55502023-07-24 16:28:41AndrosLámpákcpp17Időlimit túllépés 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;
	}

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2096 KiB
2Elfogadva3ms2580 KiB
subtask20/15
3Időlimit túllépés1.052s2772 KiB
4Futási hiba59ms131508 KiB
5Futási hiba86ms131268 KiB
subtask30/10
6Időlimit túllépés1.062s3436 KiB
7Időlimit túllépés1.069s3708 KiB
8Elfogadva795ms5820 KiB
9Elfogadva626ms6036 KiB
10Elfogadva200ms6272 KiB
subtask40/30
11Időlimit túllépés1.069s3412 KiB
12Időlimit túllépés1.046s4616 KiB
13Időlimit túllépés1.07s3492 KiB
14Időlimit túllépés1.074s3920 KiB
15Időlimit túllépés1.06s3836 KiB
16Időlimit túllépés1.07s3512 KiB
17Időlimit túllépés1.06s3536 KiB
subtask50/45
18Futási hiba79ms129936 KiB
19Futási hiba68ms129908 KiB
20Futási hiba68ms129660 KiB
21Futási hiba65ms129672 KiB
22Futási hiba75ms129640 KiB
23Futási hiba103ms129612 KiB
24Futási hiba87ms129384 KiB
25Futási hiba100ms129220 KiB
26Futási hiba100ms128984 KiB
27Futási hiba90ms128960 KiB
28Időlimit túllépés1.072s65528 KiB
29Időlimit túllépés1.062s65548 KiB