# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
846848 | 2023-09-08T14:21:08 Z | ogkostya | 참나무 (IOI23_beechtree) | C++17 | 78 ms | 13256 KB |
#include "beechtree.h" #include <algorithm> #include <queue> #include <set> #include <utility> int cn[200010]; int lev[200010]; std::vector<int> down[200010]; std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) { std::vector<int> ans{ }; bool sub2 = true; for (int i = 1; sub2 && i < N; i++) { sub2 &= P[i] == i - 1; } if (sub2) { ans.push_back(1); ans.push_back(1); for (int i = N - 3; i >= 0; i--) { sub2 &= C[i + 1] == C[N - 1]; ans.push_back(sub2 ? 1 : 0); } std::reverse(ans.begin(), ans.end()); return ans; } // sub 4 std::fill_n(cn, M + 1, 0); bool sub4 = true; for (size_t i = 0; i < C.size(); i++) { if (++cn[C[i]] > 2) { sub4 = false; break; } } for (int i = 1; i < N; i++) { down[P[i]].push_back(i); } std::queue<int> q = {}; std::fill_n(lev, N + 1, 0); std::fill_n(cn, N + 1, 0); for (int i = 0; i < N; i++) { cn[i] = down[i].size(); if (down[i].size() == 0) { q.push(i); } } while (q.size() > 0) { int ii = q.front(); q.pop(); if (ii == 0) break; if (--cn[P[ii]] == 0) { q.push(P[ii]); lev[P[ii]] = 1 + lev[ii]; } } for (int i = 0; i < N; i++) { if (i == 0 && !sub4 && lev[i] == 2) { std::set<int> s = {}; bool ok = true; std::vector<std::pair<int, int>> sort = {}; for (size_t j = 0; j < down[0].size(); j++) { if (s.count(C[down[0][j]]) == 0) { s.insert(C[down[0][j]]); sort.push_back(std::make_pair(down[down[0][j]].size(), down[0][j])); } else { ok = false; break; } } if (ok) { std::sort(sort.begin(), sort.end()); std::reverse(sort.begin(), sort.end()); for (size_t k = 0; ok && i < sort.size(); k++) { std::set<int> next = {}; int index = sort[k].second; for (size_t j = 0; j < down[index].size(); j++) { if (s.count(C[down[index][j]]) == 1 && next.count(C[down[index][j]]) == 0) { next.insert(C[down[index][j]]); } else { ok = false; break; } } s = next; } } ans.push_back(ok ? 1 : 0); } else if (lev[i] == 0) { ans.push_back(1); } else if (lev[i] == 1) { std::set<int> s = {}; bool ok = true; for (size_t j = 0; j < down[i].size(); j++) { if (s.count(C[down[i][j]]) == 0) { s.insert(C[down[i][j]]); } else { ok = false; break; } } ans.push_back(ok ? 1 : 0); } else if (lev[i] == 2) { std::set<int> s = {}; bool ok = true; int f = -1; for (size_t j = 0; j < down[i].size(); j++) { if (down[down[i][j]].size() > 0) { if (f == -1) { f = down[i][j]; } else { ok = false; break; } } if (s.count(C[down[i][j]]) == 0) { s.insert(C[down[i][j]]); } else { ok = false; break; } } if (ok) { for (size_t j = 0; j < down[f].size(); j++) { if (s.count(C[down[f][j]]) == 1) { s.erase(C[down[f][j]]); } else { ok = false; break; } } } ans.push_back(ok ? 1 : 0); } else { ans.push_back(0); } } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 1 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5468 KB | Output is correct |
5 | Correct | 1 ms | 5468 KB | Output is correct |
6 | Correct | 1 ms | 5468 KB | Output is correct |
7 | Correct | 2 ms | 5468 KB | Output is correct |
8 | Correct | 1 ms | 5464 KB | Output is correct |
9 | Correct | 2 ms | 5464 KB | Output is correct |
10 | Correct | 1 ms | 5468 KB | Output is correct |
11 | Correct | 2 ms | 5464 KB | Output is correct |
12 | Correct | 1 ms | 5468 KB | Output is correct |
13 | Correct | 1 ms | 5468 KB | Output is correct |
14 | Correct | 1 ms | 5720 KB | Output is correct |
15 | Correct | 1 ms | 5464 KB | Output is correct |
16 | Correct | 2 ms | 5464 KB | Output is correct |
17 | Correct | 1 ms | 5468 KB | Output is correct |
18 | Correct | 1 ms | 5468 KB | Output is correct |
19 | Correct | 1 ms | 5468 KB | Output is correct |
20 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
21 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 1 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5468 KB | Output is correct |
5 | Correct | 1 ms | 5468 KB | Output is correct |
6 | Correct | 1 ms | 5468 KB | Output is correct |
7 | Correct | 47 ms | 9672 KB | Output is correct |
8 | Correct | 47 ms | 9684 KB | Output is correct |
9 | Correct | 1 ms | 5464 KB | Output is correct |
10 | Correct | 1 ms | 5468 KB | Output is correct |
11 | Correct | 1 ms | 5464 KB | Output is correct |
12 | Correct | 1 ms | 5468 KB | Output is correct |
13 | Correct | 2 ms | 5468 KB | Output is correct |
14 | Correct | 2 ms | 5468 KB | Output is correct |
15 | Correct | 2 ms | 5468 KB | Output is correct |
16 | Correct | 2 ms | 5468 KB | Output is correct |
17 | Correct | 45 ms | 9684 KB | Output is correct |
18 | Correct | 53 ms | 9792 KB | Output is correct |
19 | Correct | 46 ms | 9676 KB | Output is correct |
20 | Correct | 46 ms | 9676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 5464 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 1 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5468 KB | Output is correct |
5 | Correct | 1 ms | 5468 KB | Output is correct |
6 | Correct | 1 ms | 5468 KB | Output is correct |
7 | Correct | 1 ms | 5468 KB | Output is correct |
8 | Correct | 1 ms | 5468 KB | Output is correct |
9 | Incorrect | 2 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 2 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5464 KB | Output is correct |
5 | Correct | 47 ms | 9672 KB | Output is correct |
6 | Correct | 47 ms | 9684 KB | Output is correct |
7 | Correct | 1 ms | 5464 KB | Output is correct |
8 | Correct | 2 ms | 5464 KB | Output is correct |
9 | Correct | 2 ms | 6236 KB | Output is correct |
10 | Correct | 3 ms | 6236 KB | Output is correct |
11 | Correct | 68 ms | 13256 KB | Output is correct |
12 | Correct | 78 ms | 12112 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 2 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5464 KB | Output is correct |
5 | Correct | 2 ms | 5464 KB | Output is correct |
6 | Correct | 1 ms | 5468 KB | Output is correct |
7 | Correct | 2 ms | 5464 KB | Output is correct |
8 | Correct | 1 ms | 5468 KB | Output is correct |
9 | Correct | 1 ms | 5468 KB | Output is correct |
10 | Correct | 1 ms | 5720 KB | Output is correct |
11 | Correct | 1 ms | 5464 KB | Output is correct |
12 | Correct | 2 ms | 5464 KB | Output is correct |
13 | Correct | 1 ms | 5468 KB | Output is correct |
14 | Correct | 1 ms | 5468 KB | Output is correct |
15 | Correct | 1 ms | 5468 KB | Output is correct |
16 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
17 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Correct | 1 ms | 5468 KB | Output is correct |
3 | Correct | 2 ms | 5468 KB | Output is correct |
4 | Correct | 1 ms | 5464 KB | Output is correct |
5 | Correct | 2 ms | 5464 KB | Output is correct |
6 | Correct | 1 ms | 5468 KB | Output is correct |
7 | Correct | 2 ms | 5464 KB | Output is correct |
8 | Correct | 1 ms | 5468 KB | Output is correct |
9 | Correct | 1 ms | 5468 KB | Output is correct |
10 | Correct | 1 ms | 5720 KB | Output is correct |
11 | Correct | 1 ms | 5464 KB | Output is correct |
12 | Correct | 2 ms | 5464 KB | Output is correct |
13 | Correct | 1 ms | 5468 KB | Output is correct |
14 | Correct | 1 ms | 5468 KB | Output is correct |
15 | Correct | 1 ms | 5468 KB | Output is correct |
16 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
17 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5468 KB | Output is correct |
2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
3 | Halted | 0 ms | 0 KB | - |