55522023-07-25 12:34:40AndrosLámpákcpp17Time limit exceeded 0/1001.1s16496 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;
	//}
	
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted21ms1964 KiB
2Accepted247ms2296 KiB
subtask20/15
3Time limit exceeded1.052s1672 KiB
4Time limit exceeded1.072s14264 KiB
5Wrong answer2ms2864 KiB
subtask30/10
6Time limit exceeded1.1s2328 KiB
7Time limit exceeded1.057s2476 KiB
8Time limit exceeded1.07s2680 KiB
9Time limit exceeded1.065s2812 KiB
10Time limit exceeded1.072s3008 KiB
subtask40/30
11Time limit exceeded1.08s3096 KiB
12Time limit exceeded1.049s3408 KiB
13Time limit exceeded1.065s3756 KiB
14Time limit exceeded1.062s3812 KiB
15Time limit exceeded1.072s3724 KiB
16Time limit exceeded1.065s3684 KiB
17Time limit exceeded1.065s3720 KiB
subtask50/45
18Wrong answer2ms4452 KiB
19Wrong answer2ms4540 KiB
20Wrong answer2ms4540 KiB
21Wrong answer3ms4552 KiB
22Wrong answer3ms4792 KiB
23Wrong answer2ms4884 KiB
24Wrong answer3ms4888 KiB
25Wrong answer3ms4888 KiB
26Wrong answer2ms4980 KiB
27Wrong answer2ms4980 KiB
28Time limit exceeded1.1s16436 KiB
29Time limit exceeded1.075s16496 KiB