oj.uz

Submission #854879

# Submission time Handle Problem Language Result Execution time Memory
854879 2023-09-29T08:49:50 Z piOOE Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 2016396 KB 
#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    vector<int> sh(C);
    sort(sh.begin(), sh.end());
    sh.resize(unique(sh.begin(), sh.end()) - sh.begin());
    M = size(sh);
    for (int i = 0; i < N; ++i) {
        C[i] = lower_bound(sh.begin(), sh.end(), C[i]) - sh.begin();
    }

    vector<int> ans(N, 1), isOk(N, 1), siz(N, 1);
    vector<vector<int>> adj(N), sub(N);

    for (int i = N - 1; i > 0; --i) {
        adj[P[i]].push_back(i);
    }

    for (int v = N - 1; v >= 0; --v) {
        static vector<int> cnt(M);
        for (int to : adj[v]) {
            cnt[C[to]] = 0;
            isOk[v] &= isOk[to];
        }
        for (int to : adj[v]) {
            siz[v] += siz[to];
            isOk[v] &= ++cnt[C[to]] == 1;
        }
        ans[v] = isOk[v];
        if (!isOk[v]) {
            continue;
        }
        for (int to : adj[v]) {
            sub[v].insert(sub[v].end(), sub[to].begin(), sub[to].end());
            sub[to].clear();
        }
        static vector<int> last(N, -1);
        last[v] = -1;
        for (int x : sub[v]) {
            last[x] = -1;
            ++cnt[C[x]];
        }
//        vector<int> ord = sub[v];
//        sort(ord.begin(), ord.end(), [&](int x, int y) { return pair{cnt[C[x]], C[x]} > pair{cnt[C[y]], C[y]}; });
//        for (int i = 0, j = 0, k = -1; i < size(ord); i = j) {
//            int sum = 0;
//            while (j < size(ord) && C[ord[j]] == C[ord[i]]) {
//                int x = ord[j++];
//                while (x != v) {
//                    x = P[x];
//                    if (last[x] == i) {
//                        break;
//                    } else if (last[x] != k) {
//                        ans[v] = 0;
//                        break;
//                    }
//                    sum += 1;
//                    last[x] = i;
//                }
//                if (!ans[v]) {
//                    break;
//                }
//            }
//            if (!ans[v] || sum != j - i) {
//                ans[v] = 0;
//                break;
//            }
//            k = i;
//        }
//        if (!ans[v]) {
//            sub[v].push_back(v);
//            continue;
//        }
        vector<int> q;
        set<pair<int, int>> st;
        st.emplace(siz[v], v);
        for (int i = 0; !st.empty() && ans[v]; ++i) {
            q.push_back(st.rbegin()->second);
            st.erase(--st.end());
            int x = q[i];
            if (i > 0) {
                int c = 0;
                for (int j = 1; j < i; ++j) {
                    c += C[q[j]] == C[x];
                }
                if (P[x] != q[c]) {
                    ans[v] = 0;
                    break;
                }
            }
            sort(adj[x].begin(), adj[x].end(), [&](int a, int b) { return siz[a] > siz[b]; });
            for (int to : adj[x]) {
                st.emplace(siz[to], to);
            }
        }
        sub[v].push_back(v);
    }

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
22 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 2172 ms 2016396 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2172 ms 2016396 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
18 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
18 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -