55522023-07-25 12:34:40AndrosLámpákcpp17Időlimit túllépés 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;
	//}
	
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva21ms1964 KiB
2Elfogadva247ms2296 KiB
subtask20/15
3Időlimit túllépés1.052s1672 KiB
4Időlimit túllépés1.072s14264 KiB
5Hibás válasz2ms2864 KiB
subtask30/10
6Időlimit túllépés1.1s2328 KiB
7Időlimit túllépés1.057s2476 KiB
8Időlimit túllépés1.07s2680 KiB
9Időlimit túllépés1.065s2812 KiB
10Időlimit túllépés1.072s3008 KiB
subtask40/30
11Időlimit túllépés1.08s3096 KiB
12Időlimit túllépés1.049s3408 KiB
13Időlimit túllépés1.065s3756 KiB
14Időlimit túllépés1.062s3812 KiB
15Időlimit túllépés1.072s3724 KiB
16Időlimit túllépés1.065s3684 KiB
17Időlimit túllépés1.065s3720 KiB
subtask50/45
18Hibás válasz2ms4452 KiB
19Hibás válasz2ms4540 KiB
20Hibás válasz2ms4540 KiB
21Hibás válasz3ms4552 KiB
22Hibás válasz3ms4792 KiB
23Hibás válasz2ms4884 KiB
24Hibás válasz3ms4888 KiB
25Hibás válasz3ms4888 KiB
26Hibás válasz2ms4980 KiB
27Hibás válasz2ms4980 KiB
28Időlimit túllépés1.1s16436 KiB
29Időlimit túllépés1.075s16496 KiB