55502023-07-24 16:28:41AndrosLámpákcpp17Time limit exceeded 0/1001.074s131508 KiB
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

#define maxN 100010
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> temp_allapot;

vector<int> solutions;//Megoldasok
void solve(int n, int k) {
	int a;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		temp_allapot[i]=a;
	}
	for (int i = 0; i < k; i++)
	{//tesztek
		for (int i = 2; i <= n; i++)
		{
			//Ha amit nezunk fel van kapcsolva
			if (temp_allapot[i]) {
				//Akkor atkapcsolja az osszes olyan tornyot, ami alatta van
				temp_allapot ^= masks[i];
			}
		}
	}
	solutions.push_back(temp_allapot[1]);//Lementjuk az 1-es villanytorony allapotat
}

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;
	}
}

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_masks(n);

	for (int i = 0; i < q; i++)
	{
		//Ellenorzesek
		solve(n, k);
	}

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

}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2096 KiB
2Accepted3ms2580 KiB
subtask20/15
3Time limit exceeded1.052s2772 KiB
4Runtime error59ms131508 KiB
5Runtime error86ms131268 KiB
subtask30/10
6Time limit exceeded1.062s3436 KiB
7Time limit exceeded1.069s3708 KiB
8Accepted795ms5820 KiB
9Accepted626ms6036 KiB
10Accepted200ms6272 KiB
subtask40/30
11Time limit exceeded1.069s3412 KiB
12Time limit exceeded1.046s4616 KiB
13Time limit exceeded1.07s3492 KiB
14Time limit exceeded1.074s3920 KiB
15Time limit exceeded1.06s3836 KiB
16Time limit exceeded1.07s3512 KiB
17Time limit exceeded1.06s3536 KiB
subtask50/45
18Runtime error79ms129936 KiB
19Runtime error68ms129908 KiB
20Runtime error68ms129660 KiB
21Runtime error65ms129672 KiB
22Runtime error75ms129640 KiB
23Runtime error103ms129612 KiB
24Runtime error87ms129384 KiB
25Runtime error100ms129220 KiB
26Runtime error100ms128984 KiB
27Runtime error90ms128960 KiB
28Time limit exceeded1.072s65528 KiB
29Time limit exceeded1.062s65548 KiB