이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "beechtree.h"
#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 get(int v, int u) {
if (g[v].size() > g[u].size())
return -1;
if (g[v].size() < g[u].size())
return 1;
for (int i = 0; i < g[v].size(); i++) {
int x = get(g[v][i].s, g[u][i].s);
if (x != 0)
return x;
}
if(tin[v] < tin[u])
return -1;
return 1;
}
bool cmp(int v, int u) {
return get(v, u) == -1;
}
void dfs(int v) {
tin[v] = timer++;
t[v].pb(v);
for (auto it: g[v]) {
int to = it.s;
dfs(to);
for (auto x: t[to])
t[v].pb(x);
}
sort(t[v].begin() + 1, t[v].end(), cmp);
bool ok = 1;
ok &= (t[v][0] == v);
for (int i = 1; i < t[v].size(); i++) {
int cnt = 0;
for (int j = 1; j < i; j++)
if (C[t[v][i]] == C[t[v][j]])
cnt++;
ok &= (t[v][cnt] == P[t[v][i]]);
}
ans[v] |= ok;
}
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();
t[i].clear();
P[i] = PP[i];
C[i] = CC[i];
ans[i] = 0;
}
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 'int get(int, int)':
beechtree.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 1; 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... |