5549 2023. 07. 24 16:21:46 Andros Lámpák cpp17 Időlimit túllépés 0/100 1.1s 131688 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;
	}

}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2092 KiB
2 Elfogadva 3ms 2588 KiB
subtask2 0/15
3 Időlimit túllépés 1.1s 2532 KiB
4 Futási hiba 71ms 131688 KiB
5 Futási hiba 76ms 131460 KiB
subtask3 0/10
6 Időlimit túllépés 1.069s 3188 KiB
7 Időlimit túllépés 1.06s 3408 KiB
8 Elfogadva 795ms 5760 KiB
9 Elfogadva 625ms 5716 KiB
10 Elfogadva 200ms 5664 KiB
subtask4 0/30
11 Időlimit túllépés 1.057s 2536 KiB
12 Időlimit túllépés 1.057s 2820 KiB
13 Időlimit túllépés 1.08s 2816 KiB
14 Időlimit túllépés 1.057s 2772 KiB
15 Időlimit túllépés 1.057s 2768 KiB
16 Időlimit túllépés 1.067s 2768 KiB
17 Időlimit túllépés 1.069s 2820 KiB
subtask5 0/45
18 Futási hiba 68ms 130608 KiB
19 Futási hiba 75ms 130368 KiB
20 Futási hiba 64ms 130356 KiB
21 Futási hiba 64ms 130328 KiB
22 Futási hiba 75ms 130092 KiB
23 Futási hiba 92ms 130084 KiB
24 Futási hiba 100ms 129844 KiB
25 Futási hiba 100ms 129608 KiB
26 Futási hiba 90ms 129368 KiB
27 Futási hiba 90ms 129172 KiB
28 Időlimit túllépés 1.052s 65296 KiB
29 Időlimit túllépés 1.072s 65408 KiB