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

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2092 KiB
2Elfogadva3ms2588 KiB
subtask20/15
3Időlimit túllépés1.1s2532 KiB
4Futási hiba71ms131688 KiB
5Futási hiba76ms131460 KiB
subtask30/10
6Időlimit túllépés1.069s3188 KiB
7Időlimit túllépés1.06s3408 KiB
8Elfogadva795ms5760 KiB
9Elfogadva625ms5716 KiB
10Elfogadva200ms5664 KiB
subtask40/30
11Időlimit túllépés1.057s2536 KiB
12Időlimit túllépés1.057s2820 KiB
13Időlimit túllépés1.08s2816 KiB
14Időlimit túllépés1.057s2772 KiB
15Időlimit túllépés1.057s2768 KiB
16Időlimit túllépés1.067s2768 KiB
17Időlimit túllépés1.069s2820 KiB
subtask50/45
18Futási hiba68ms130608 KiB
19Futási hiba75ms130368 KiB
20Futási hiba64ms130356 KiB
21Futási hiba64ms130328 KiB
22Futási hiba75ms130092 KiB
23Futási hiba92ms130084 KiB
24Futási hiba100ms129844 KiB
25Futási hiba100ms129608 KiB
26Futási hiba90ms129368 KiB
27Futási hiba90ms129172 KiB
28Időlimit túllépés1.052s65296 KiB
29Időlimit túllépés1.072s65408 KiB