# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
442384 | koioi.org-koosaga | Counterspells (CPSPC17_counterspells) | C++17 | 1087 ms | 5700 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |