This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "beechtree.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e3 + 5;
vector<pii> g[nmax];
vector<int> P, C;
unordered_set<int> colors[nmax], play[nmax];
bool isanc(unordered_set<int>& A, unordered_set<int>& B) {
if(sz(A) < sz(B)) return 0;
for(auto &x : B)
if(!A.count(x)) return 0;
return 1;
}
vector<int> sol;
int h[nmax];
bool SI[nmax][nmax];
bool calc[nmax][nmax];
bool superimposable(int x, int y) { // x peste y
//if(sz(g[x]) == 0 || x == y) return 1;
//if(calc[x][y]) return SI[x][y];
map<int, int> gy;
for(auto [a, c] : g[y]) gy[c] = a;
//calc[x][y] = 1;
//SI[x][y] = 1;
for(auto [a, c] : g[x]) {
if(gy.count(c) == 0) { return 0; }
if(!superimposable(a, gy[c])) { return 0; }
}
return 1;
}
int area[nmax];
vector<int> dfs(int node) {
vector<int> here;
sol[node] = 1;
area[node] = 1;
here.emplace_back(node);
for(auto [x, c] : g[node]) {
auto T = dfs(x);
area[node] += area[x];
sol[node] &= sol[x];
copy(all(T), back_inserter(here));
}
if(sz(g[node]) != sz(colors[node])) sol[node] = 0;
if(sol[node] == 0) { return here; }
sort(all(here), [&](int a, int b) { return area[a] < area[b]; });
for(int i = 0; sol[node] && i < sz(here) - 1; i++)
if(!superimposable(here[i], here[i + 1])) { sol[node] = 0; }
return here;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P_, std::vector<int> C_) {
P = P_;
C = C_;
for(int i = 1; i < N; i++) {
g[P[i]].emplace_back(i, C[i]);
colors[P[i]].emplace(C[i]);
}
sol.assign(N, 0);
dfs(0);
return sol;
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
# | 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... |