Submission #442384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442384	2021-07-07T15:50:31 Z	koioi.org-koosaga	Counterspells (CPSPC17_counterspells)	C++17	60 / 100	1000 ms	5700 KB

Main

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
const int mod = 1e9 + 7;

int n, p[MAXN], dep[MAXN];
int val[MAXN], cnt[MAXN][2];

int main(){
	scanf("%d",&n);
	p[0] = -1;
	for(int i = 1; i <= n; i++){
		scanf("%d",&p[i]);
		dep[i] = dep[p[i]] + 1;
	}
	for(int i = 1; i <= n; i++){
		val[i] = dep[i] % 2;
		cnt[p[i]][val[i]]++;
		int ans = 0;
		for(int j = p[i]; j != -1; j = p[j]){
			int cur = val[j];
			int nxt = -1;
			if(dep[j] % 2 == 0) nxt = (cnt[j][1] ? 1 : 0);
			else nxt = (cnt[j][0] ? 0 : 1);
			if(cur != nxt){
				val[j] ^= 1;
				if(~p[j]){
					cnt[p[j]][val[j]]++;
					cnt[p[j]][val[j]^1]--;
				}
				ans++;
			}
			else break;
		}
		printf("%d\n", ans);
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
Main.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d",&p[i]);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	181 ms	480 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	3 ms	460 KB	Output is correct
13	Correct	9 ms	560 KB	Output is correct
14	Correct	30 ms	460 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	181 ms	480 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	3 ms	460 KB	Output is correct
13	Correct	9 ms	560 KB	Output is correct
14	Correct	30 ms	460 KB	Output is correct
15	Correct	26 ms	2808 KB	Output is correct
16	Execution timed out	1087 ms	2076 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	5700 KB	Output is correct
2	Correct	45 ms	4828 KB	Output is correct
3	Correct	32 ms	2944 KB	Output is correct
4	Correct	46 ms	5444 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	181 ms	480 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	3 ms	460 KB	Output is correct
13	Correct	9 ms	560 KB	Output is correct
14	Correct	30 ms	460 KB	Output is correct
15	Correct	26 ms	2808 KB	Output is correct
16	Execution timed out	1087 ms	2076 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-