이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
vector<pii> g[N];
int n, m;
int ans[N];
int P[N], C[N];
int tin[N], timer;
vector<int> t[N];
int sz[N];
map<int, int> was[N], dp[N];
bool f(int v, int u) {
if (was[v][u])
return dp[v][u];
was[v][u] = 1;
for (int i = 0, j = 0; i < g[u].size(); i++) {
while (j < g[v].size() && g[v][j].f != g[u][i].f)
j++;
if (j == g[v].size())
return dp[v][u] = false;
if (!f(g[v][j].s, g[u][i].s))
return dp[v][u] = false;
}
return dp[v][u] = true;
}
void dfs(int v) {
tin[v] = timer++;
sz[v] = 1;
ans[v] = 1;
t[v].pb(v);
vector<int> a;
for (int i = 0; i + 1 < g[v].size(); i++)
ans[v] &= (g[v][i].f != g[v][i + 1].f);
for (auto it: g[v]) {
int to = it.s;
a.pb(to);
dfs(to);
sz[v] += sz[to];
ans[v] &= ans[to];
ans[v] &= f(v, to);
for(auto x : t[to])
t[v].pb(x);
}
sort(a.begin(), a.end(), [](int i, int j) {
return sz[i] > sz[j];
});
for (int i = 0; i + 1 < a.size(); i++)
ans[v] &= f(a[i], a[i + 1]);
sort(t[v].begin(), t[v].end(), [](int i, int j) {
return g[i].size() < g[j].size();
});
set<int> st;
for (int i = 0; i < t[v].size(); i++) {
int u = t[v][i];
vector<int> c;
for (auto x: g[u]) {
c.pb(x.f);
st.insert(x.f);
}
vector<int> cc(st.begin(), st.end());
ans[v] &= (c == cc);
}
}
vector<int> beechtree(int N, int M, vector<int> PP, vector<int> CC) {
n = N;
for (int i = 0; i < n; i++) {
g[i].clear();
P[i] = PP[i];
C[i] = CC[i];
ans[i] = 0;
was[i].clear();
dp[i].clear();
t[i].clear();
}
for (int i = 1; i < n; i++)
g[P[i]].pb({C[i], i});
for (int i = 0; i < n; i++)
sort(g[i].begin(), g[i].end());
dfs(0);
return vector<int>(ans, ans + n);
}
컴파일 시 표준 에러 (stderr) 메시지
beechtree.cpp: In function 'bool first(int, int)':
beechtree.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0, j = 0; i < g[u].size(); i++) {
| ~~^~~~~~~~~~~~~
beechtree.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (j < g[v].size() && g[v][j].f != g[u][i].f)
| ~~^~~~~~~~~~~~~
beechtree.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (j == g[v].size())
| ~~^~~~~~~~~~~~~~
beechtree.cpp:37:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
37 | return dp[v][u] = false;
beechtree.cpp:39:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
39 | return dp[v][u] = false;
beechtree.cpp:41:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
41 | return dp[v][u] = true;
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i + 1 < g[v].size(); i++)
| ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i + 1 < a.size(); i++)
| ~~~~~~^~~~~~~~~~
beechtree.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < t[v].size(); i++) {
| ~~^~~~~~~~~~~~~
# | 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... |