Submission #442400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442400	2021-07-07T16:59:08 Z	koioi.org-koosaga	Counterspells (CPSPC17_counterspells)	C++17	60 / 100	1000 ms	3780 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];
 
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;
		if(dep[i] % 2) cnt[i]++;
	}
	for(int i = 1; i <= n; i++){
		val[i] = dep[i] % 2;
		if(dep[i] % 2) cnt[p[i]]++;
		else cnt[p[i]]--;
		int ans = 0;
		for(int j = p[i]; j != -1; j = p[j]){
			int cur = val[j];
			int nxt = (cnt[j] > 0);
			if(cur != nxt){
				val[j] ^= 1;
				if(~p[j]){
					if(val[j] == 1) cnt[p[j]]++;
					else cnt[p[j]]--;
				}
				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	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	120 ms	464 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	8 ms	460 KB	Output is correct
14	Correct	20 ms	452 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	120 ms	464 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	8 ms	460 KB	Output is correct
14	Correct	20 ms	452 KB	Output is correct
15	Correct	26 ms	1956 KB	Output is correct
16	Execution timed out	1084 ms	2008 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	3780 KB	Output is correct
2	Correct	44 ms	3564 KB	Output is correct
3	Correct	33 ms	3088 KB	Output is correct
4	Correct	44 ms	3776 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	120 ms	464 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	8 ms	460 KB	Output is correct
14	Correct	20 ms	452 KB	Output is correct
15	Correct	26 ms	1956 KB	Output is correct
16	Execution timed out	1084 ms	2008 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-