Submission #442399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442399	2021-07-07T16:55:58 Z	koioi.org-koosaga	Counterspells (CPSPC17_counterspells)	C++17	60 / 100	1000 ms	4468 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], deg[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;
	}
	for(int i = 1; i <= n; i++){
		val[i] = dep[i] % 2;
		if(dep[i] % 2) cnt[p[i]]++;
		deg[p[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] > 0);
			else nxt = (cnt[j] > deg[j] - 1);
			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	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 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	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 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	127 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	4 ms	420 KB	Output is correct
13	Correct	9 ms	460 KB	Output is correct
14	Correct	22 ms	604 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	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 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	127 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	4 ms	420 KB	Output is correct
13	Correct	9 ms	460 KB	Output is correct
14	Correct	22 ms	604 KB	Output is correct
15	Correct	26 ms	2296 KB	Output is correct
16	Execution timed out	1091 ms	1660 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	4468 KB	Output is correct
2	Correct	46 ms	3616 KB	Output is correct
3	Correct	41 ms	2528 KB	Output is correct
4	Correct	48 ms	3780 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	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 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	127 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	4 ms	420 KB	Output is correct
13	Correct	9 ms	460 KB	Output is correct
14	Correct	22 ms	604 KB	Output is correct
15	Correct	26 ms	2296 KB	Output is correct
16	Execution timed out	1091 ms	1660 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-