oj.uz

Submission #428421

# Submission time Handle Problem Language Result Execution time Memory
428421 2021-06-15T11:39:20 Z 최서현(#7487) Counterspells (CPSPC17_counterspells) C++17
60 / 100
 1000 ms 12928 KB 
#include <iostream>
#include <vector>

using namespace std;

vector<int> gph[202020];
int par[202020];
int cnt[202020];

void dfs(int x)
{
    for(auto y : gph[x])
    {
        dfs(y);
        if(!cnt[y]) ++cnt[x];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("input.txt", "r", stdin);

    int n; cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        par[i] = x;
        gph[x].push_back(i);
    }

    dfs(0);

    int ret[n];
    for(int i = n; i >= 1; --i)
    {
        int ans = 0;
        int x = par[i];
        int del = -1;
        while(1)
        {
            int __del = ((!(cnt[x] + del)) - (!cnt[x]));
            cnt[x] += del;
            del = __del;
            if(!del) break;
            ++ans;
            if(!x) break;
            x = par[x];
        }
        ret[i - 1] = ans;
    }

    for(auto i : ret) cout << i << '\n';
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 7 ms 5324 KB Output is correct
9 Correct 106 ms 5892 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 7 ms 5324 KB Output is correct
13 Correct 10 ms 5452 KB Output is correct
14 Correct 20 ms 5388 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 7 ms 5324 KB Output is correct
9 Correct 106 ms 5892 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 7 ms 5324 KB Output is correct
13 Correct 10 ms 5452 KB Output is correct
14 Correct 20 ms 5388 KB Output is correct
15 Correct 37 ms 7876 KB Output is correct
16 Execution timed out 1089 ms 12928 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10948 KB Output is correct
2 Correct 56 ms 10344 KB Output is correct
3 Correct 31 ms 7360 KB Output is correct
4 Correct 50 ms 11196 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5192 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 7 ms 5324 KB Output is correct
9 Correct 106 ms 5892 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 5 ms 5196 KB Output is correct
12 Correct 7 ms 5324 KB Output is correct
13 Correct 10 ms 5452 KB Output is correct
14 Correct 20 ms 5388 KB Output is correct
15 Correct 37 ms 7876 KB Output is correct
16 Execution timed out 1089 ms 12928 KB Time limit exceeded
17 Halted 0 ms 0 KB -