5552 2023. 07. 25 12:34:40 Andros Lámpák cpp17 Időlimit túllépés 0/100 1.1s 16496 KiB
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

#define maxN 10000
bitset<maxN> tornyok = 0b0;//A tornyok alapveto allapota, semmi sincs bekapcsolva
int megelozesek[maxN];//Ha i-t megelozi j, akkor megelozesek[i]=j
bitset<maxN> masks[maxN];//A maszkok
//Ha az i vilagitorony jelet kuld, akkor atkapcsol minden masks[i]-ben levo torony
//Ezt egy xor-al lehet modellezni

bitset<maxN> felette[maxN];//felette[i]: az i felett milyen tornyok vannak
bitset<maxN> alatta[maxN];


void generate_masks(int n) {
	//Legeneralja egy-egy toronyra az osszes tornyot,
	//amit at kell kapcsolni, ha azt aktivaljuk
	bitset<maxN> temp_mask;
	for (int i = 2; i <= n; i++)
	{
		temp_mask = 0b0;//alapbol semmit se ertesit
		temp_mask[megelozesek[i]] = 1;//Amit o ertesit, azt bekapcsoljuk
		temp_mask |= masks[megelozesek[i]];//Aztan mindent ertesit, amit az ot megelozo is
		masks[i] = temp_mask;
	}
}

//Legenralja az aktivalasi lancokat
void generate_lancok(int n){
	for (int u = 2; u <= n; u++) //v<-u
	{
		int v = megelozesek[u];
		felette[v][u] = 1;//V fele berakjuk u-t
		alatta[u] = alatta[v];//U alatt pontosan az lesz, mint v alatt
		alatta[u][v] = 1;//csak V is benne lesz
		for (int i = 0; i < maxN; i++)
		{
			if (alatta[v][i]) {//Minden v alatt levore
				//Ha alatta van
				//akkor fele rakjuk u-t
				felette[i][u] = 1;
			}
		}
	}
	
}

bitset<maxN> alapallas = 0b0;
int main()
{
	int n, k, q;
	cin >> n >> k >> q;

	if (maxN < n) {
		cout << "maxN tul kicsi!";
		return 0;
	}

	for (int i = 2; i <= n; i++)
	{
		cin >> megelozesek[i];
	}

	generate_lancok(n);


	vector<int> mo;//vektorba mennek a megoldasok, mert kulonben egy-egy alapallas kozott irna ki

	for (int i = 0; i < q; i++)
	{
		alapallas = 0b0;//Reset
		//Beolvasom a tornyok alapallasat
		for (int j = 1; j <= n; j++)
		{
			int a;
			cin >> a;
			alapallas[j] = a;
		}


		for (int proba = 0; proba < k; proba++)
		{
			for (int j = 0; j < maxN; j++)
			{
				//j torony akkor atkapcsol, ha a felette levo bekapcsolt tornyok szama paratlan
				if ((felette[j] & alapallas).count() % 2 == 1) {
					alapallas[j] = ~alapallas[j];
				}
			}
			//alapallast nem kell kimenteni kulon temp-be, mert nem fogja az algoritmus megvaltoztatni
			//Hiszen csak akkor valtoztatna, ha felfele is menne a valtozas
			//De ahhoz az kell, hogy a lenti allapotok befolyasoljak a fenti tornyokat
			//Lehet ettol lassu, mert nem tudja kioptimalizalni a barnch prediction
			//Ifet megprobalhatom bitwise cuccokkal
		}
		//cout << alapallas[1]<<endl;//Kiirjuk az 1-es tornyot
		mo.push_back(alapallas[1]);
	}

	for (int e : mo) {
		cout << e << endl;
	}

	//for (int i = 0; i < maxN; i++)
	//{
	//	cout << i << ":\t" << felette[i]<<endl;
	//}
	
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 21ms 1964 KiB
2 Elfogadva 247ms 2296 KiB
subtask2 0/15
3 Időlimit túllépés 1.052s 1672 KiB
4 Időlimit túllépés 1.072s 14264 KiB
5 Hibás válasz 2ms 2864 KiB
subtask3 0/10
6 Időlimit túllépés 1.1s 2328 KiB
7 Időlimit túllépés 1.057s 2476 KiB
8 Időlimit túllépés 1.07s 2680 KiB
9 Időlimit túllépés 1.065s 2812 KiB
10 Időlimit túllépés 1.072s 3008 KiB
subtask4 0/30
11 Időlimit túllépés 1.08s 3096 KiB
12 Időlimit túllépés 1.049s 3408 KiB
13 Időlimit túllépés 1.065s 3756 KiB
14 Időlimit túllépés 1.062s 3812 KiB
15 Időlimit túllépés 1.072s 3724 KiB
16 Időlimit túllépés 1.065s 3684 KiB
17 Időlimit túllépés 1.065s 3720 KiB
subtask5 0/45
18 Hibás válasz 2ms 4452 KiB
19 Hibás válasz 2ms 4540 KiB
20 Hibás válasz 2ms 4540 KiB
21 Hibás válasz 3ms 4552 KiB
22 Hibás válasz 3ms 4792 KiB
23 Hibás válasz 2ms 4884 KiB
24 Hibás válasz 3ms 4888 KiB
25 Hibás válasz 3ms 4888 KiB
26 Hibás válasz 2ms 4980 KiB
27 Hibás válasz 2ms 4980 KiB
28 Időlimit túllépés 1.1s 16436 KiB
29 Időlimit túllépés 1.075s 16496 KiB