55492023-07-24 16:21:46AndrosLámpákcpp17Time limit exceeded 0/1001.1s131688 KiB
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

#define maxN 100001
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
1Accepted3ms2092 KiB
2Accepted3ms2588 KiB
subtask20/15
3Time limit exceeded1.1s2532 KiB
4Runtime error71ms131688 KiB
5Runtime error76ms131460 KiB
subtask30/10
6Time limit exceeded1.069s3188 KiB
7Time limit exceeded1.06s3408 KiB
8Accepted795ms5760 KiB
9Accepted625ms5716 KiB
10Accepted200ms5664 KiB
subtask40/30
11Time limit exceeded1.057s2536 KiB
12Time limit exceeded1.057s2820 KiB
13Time limit exceeded1.08s2816 KiB
14Time limit exceeded1.057s2772 KiB
15Time limit exceeded1.057s2768 KiB
16Time limit exceeded1.067s2768 KiB
17Time limit exceeded1.069s2820 KiB
subtask50/45
18Runtime error68ms130608 KiB
19Runtime error75ms130368 KiB
20Runtime error64ms130356 KiB
21Runtime error64ms130328 KiB
22Runtime error75ms130092 KiB
23Runtime error92ms130084 KiB
24Runtime error100ms129844 KiB
25Runtime error100ms129608 KiB
26Runtime error90ms129368 KiB
27Runtime error90ms129172 KiB
28Time limit exceeded1.052s65296 KiB
29Time limit exceeded1.072s65408 KiB