oj.uz

답안 #428421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -