이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "beechtree.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
using namespace std;
const int N = 2e5 + 10;
vector <vector<pair<int, int>>> G;
vector <pair<int, int>> get_subtree(int v, int c) {
vector <pair<int, int>> cur;
cur.push_back({ v, c });
for (auto it : G[v]) {
for (auto& j : get_subtree(it.first, it.second)) {
cur.push_back(j);
}
}
return cur;
}
bool check(vector <pair<int, int>>& w, vector <int>& P, vector <int>& C) {
map <int, int> mp;
for (int i = 1; i < (int)w.size(); i++) {
if (P[w[i].first] != w[mp[w[i].second]].first) return false;
mp[w[i].second]++;
}
return true;
}
bool cmp(set <int> x, set <int> y) {
return (int)x.size() > (int)y.size();
}
vector <int> beechtree(int N, int M, vector <int> P, vector <int> C) {
bool subtask1 = (N <= 8);
bool subtask2 = true;
bool subtask3 = true;
bool subtask4 = true;
G.clear();
G.resize(N);
map <int, int> mp;
for (int i = 1; i < N; i++) {
if (P[i] != (i - 1)) {
subtask2 = false;
}
G[P[i]].push_back({ i, C[i] });
mp[C[i]]++;
if (P[i] != 0 && P[P[i]] != 0) {
subtask3 = false;
}
}
for (auto it : mp) {
if (it.second > 2) {
subtask4 = false;
}
}
if (subtask1) {
vector <int> ret = {};
for (int i = 0; i < N; i++) {
vector <pair<int, int>> w = get_subtree(i, C[i]);
sort(w.begin() + 1, w.end());
bool ch = false;
if (check(w, P, C)) ch = true;
while (next_permutation(w.begin() + 1, w.end())) {
if (check(w, P, C)) ch = true;
}
ret.push_back(ch);
}
return ret;
}
if (subtask2) {
vector <int> ret = {};
if (N == 1) return { 1 };
int cnt = 2;
for (int i = N - 2; i > 0; i--) {
if (C[i] != C[N - 1]) break;
cnt++;
}
for (int i = 0; i < N - cnt; i++) {
ret.push_back(0);
}
for (int i = 0; i < cnt; i++) {
ret.push_back(1);
}
return ret;
}
if (subtask3) {
bool esim = true;
vector <int> ret(N, 0);
vector <set<int>> sets;
for (int i = N - 1; i >= 1; i--) {
if (G[i].empty()) {
ret[i] = 1;
}
else {
bool ch = true;
set <int> ms;
for (auto it : G[i]) {
if (ms.find(it.second) != ms.end()) {
esim = false;
ch = false;
}
ms.insert(it.second);
}
if (ch) {
ret[i] = 1;
sets.push_back(ms);
}
}
}
if (!esim) return ret;
set <int> ms;
for (auto it : G[0]) {
if (ms.find(it.second) != ms.end()) {
return ret;
}
ms.insert(it.second);
}
sort(sets.begin(), sets.end(), cmp);
for (auto& it : sets) {
for (auto& j : it) {
if (ms.find(j) == ms.end()) {
return ret;
}
}
ms = it;
}
ret[0] = 1;
return ret;
}
if (subtask4) {
vector <int> ret(N, 0);
vector <bool> lvl1(N, 0);
vector <bool> different(N, true);
vector <set<int>> sets(N, set<int>());
for (int v = N - 1; v >= 0; v--) {
if (G[v].empty()) {
ret[v] = 1;
continue;
}
lvl1[v] = true;
for (auto &it : G[v]) {
if (!G[it.first].empty()) lvl1[v] = false;
}
if (lvl1[v]) {
for (auto &it : G[v]) {
if (sets[v].find(it.second) != sets[v].end()) {
different[v] = false;
}
sets[v].insert(it.second);
}
if (different[v]) {
ret[v] = 1;
continue;
}
}
bool lvl2 = true;
for (auto it : G[v]) {
if (!G[it.first].empty() && !lvl1[it.first]) {
lvl2 = false;
}
}
if (!lvl2) continue;
bool ch = true;
for (auto it : G[v]) {
if (!different[it.first]) ch = false;
}
set <int> ms;
for (auto it : G[v]) {
if (ms.find(it.second) != ms.end()) {
ch = false;
}
ms.insert(it.second);
}
vector <set<int>> cur_sets;
for (auto it : G[v]) {
if (!G[it.first].empty()) cur_sets.push_back(sets[it.first]);
}
sort(cur_sets.begin(), cur_sets.end(), cmp);
for (auto& it : cur_sets) {
for (auto& j : it) {
if (ms.find(j) == ms.end()) {
ch = false;
}
}
ms = it;
}
ret[v] = ch;
}
}
}
/*
int main() {
for (auto it : beechtree(5, 2, { -1, 0, 1, 2, 3 }, { 0, 1, 2, 2, 2 })) {
cout << it << " ";
}
}
*/
컴파일 시 표준 에러 (stderr) 메시지
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:39:17: warning: control reaches end of non-void function [-Wreturn-type]
39 | map <int, int> mp;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |