5550 2023. 07. 24 16:28:41 Andros Lámpák cpp17 Időlimit túllépés 0/100 1.074s 131508 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;
	}

}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2096 KiB
2 Elfogadva 3ms 2580 KiB
subtask2 0/15
3 Időlimit túllépés 1.052s 2772 KiB
4 Futási hiba 59ms 131508 KiB
5 Futási hiba 86ms 131268 KiB
subtask3 0/10
6 Időlimit túllépés 1.062s 3436 KiB
7 Időlimit túllépés 1.069s 3708 KiB
8 Elfogadva 795ms 5820 KiB
9 Elfogadva 626ms 6036 KiB
10 Elfogadva 200ms 6272 KiB
subtask4 0/30
11 Időlimit túllépés 1.069s 3412 KiB
12 Időlimit túllépés 1.046s 4616 KiB
13 Időlimit túllépés 1.07s 3492 KiB
14 Időlimit túllépés 1.074s 3920 KiB
15 Időlimit túllépés 1.06s 3836 KiB
16 Időlimit túllépés 1.07s 3512 KiB
17 Időlimit túllépés 1.06s 3536 KiB
subtask5 0/45
18 Futási hiba 79ms 129936 KiB
19 Futási hiba 68ms 129908 KiB
20 Futási hiba 68ms 129660 KiB
21 Futási hiba 65ms 129672 KiB
22 Futási hiba 75ms 129640 KiB
23 Futási hiba 103ms 129612 KiB
24 Futási hiba 87ms 129384 KiB
25 Futási hiba 100ms 129220 KiB
26 Futási hiba 100ms 128984 KiB
27 Futási hiba 90ms 128960 KiB
28 Időlimit túllépés 1.072s 65528 KiB
29 Időlimit túllépés 1.062s 65548 KiB