oj.uz

답안 #1058505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058505 2024-08-14T10:22:55 Z mc061 참나무 (IOI23_beechtree) C++17
0 / 100
 24 ms 7284 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3+1;

int cnt[N]={};
vector<int> tree[N];
int c[N]={};
int p[N]={};
int depth[N]={};

map<int, int> inside[1001];
map<int, int> supposed[1001];

bool cmp(map<int, int>& mp1, map<int, int>& mp2) {
    if (mp1.size() != mp2.size()) return false;
    for (auto it = mp1.begin(); it != mp1.end(); ++it) {
        int key = it->first;
        auto it2 = mp2.lower_bound(key);
        if (it2 == mp2.end() || it2->first != key || it2->second != it->second) return false;
    }
    return true;
}


vector<vector<int>> by_depths(N);
bool ck(vector<int> sub) {
    memset(cnt, 0, sizeof(cnt));
    int sz = sub.size();
    if (sz == 1) return true;
    vector<int> depths(sz, 0);
    vector<bool> matched(sz, false);
    vector<int> now(sz, -1);
    for (int i = 0; i < sz; ++i) {
        inside[i].clear();
        depths[i] = depth[sub[i]];
    }
    for (int i = depths[0]; i <= depths.back(); ++i) by_depths[i].clear();
    for (int i = 0; i < sz; ++i) by_depths[depths[i]].push_back(sub[i]);
    for (int i = 1; i < sz; ++i) {
        int par = cnt[c[sub[i]]];
        inside[par][c[sub[i]]]++;
        if (depths[par] != depth[sub[i]]-1) return false;
        cnt[c[sub[i]]]++;
    }

    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j < sz; ++j) {
            if (matched[j]) continue;
            if (depths[i] == depths[j] && cmp(inside[i], supposed[sub[j]])) {
                matched[j] = true;
                now[i] = j;
                break;
            }
        }
        if (now[i] == -1) return false;
    }
    for (int i = 1; i < sz; ++i) {
        cnt[c[sub[i]]]--;
    }

    for (int i = 1; i < sz; ++i) {
        int par = cnt[c[now[i]]];
        if (p[now[i]] != now[par]) return false;
        cnt[c[now[i]]]++;
    }
    return true;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
    for (int i = 1; i < N; ++i) {
        p[i] = P[i];
        tree[i].push_back(p[i]);
        tree[p[i]].push_back(i);
        c[i] = C[i];
    }
    auto dfs = [&] (auto&& self, int v, int d=0) -> void {
        depth[v] = d;
        for (int u : tree[v]) if (u != p[v]) {
            self(self, u, d+1);
        }
    };
    dfs(dfs, 0);
    vector<int> res(N);
    for (int i = 0; i < N; ++i) {
        for (int u : tree[i]) if (u != p[i]) {
            supposed[i][c[u]]++;
        }
    }
    for (int i = 0; i < N; ++i) {
        vector<int> sub = {};
        auto bfs = [&] (int s) -> void {
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                sub.push_back(v);
                for (int u : tree[v]) if (u != p[v]) {
                    q.push(u);
                }
            }
        };
        bfs(i);
        res[i] = ck(sub);
    }
    return res;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 4th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 24 ms 7284 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
7 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -