이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int SZ = 1 << 17;
vector<int> TG[SZ], G[SZ], EG[SZ];
pii E[SZ];
int D[SZ], P[SZ], Z[SZ], R[SZ], in[SZ], out[SZ], dn;
int ES[SZ], C[SZ], ind[SZ];
void MakeG(int cur, int prev) {
P[cur] = prev;
D[cur] = D[prev] + 1;
for (int next : TG[cur]) {
if (next == prev) continue;
G[cur].push_back(next);
MakeG(next, cur);
}
}
int DFS(int cur) {
int& ret = Z[cur] = 1;
for (int i = 0; i < G[cur].size(); ++i) {
int next = G[cur][i];
ret += DFS(next);
if (Z[next] > Z[G[cur][0]]) swap(G[cur][0], G[cur][i]);
}
return ret;
}
void DFS2(int cur, int top) {
in[cur] = ++dn;
R[cur] = top;
for (int i = 0; i < G[cur].size(); ++i) {
int next = G[cur][i];
DFS2(next, (i == 0 ? top : next));
}
out[cur] = dn;
}
void DFS3(int cur, int pe) {
if (pe != -1 && ES[cur] >= 0) {
EG[ES[cur]].push_back(pe);
ind[pe]++;
for (int next : G[cur]) DFS3(next, ES[cur]);
}
else for (int next : G[cur]) DFS3(next, pe);
}
int LCA(int a, int b) {
while (R[a] != R[b]) {
if (D[R[a]] > D[R[b]]) swap(a, b);
b = P[R[b]];
}
return (D[a] < D[b] ? a : b);
}
struct Seg {
int T[SZ << 1];
void Clear() {
memset(T, -1, sizeof(T));
}
void Update(int i, int v) {
T[i += SZ - 1] = v;
while (i >>= 1) T[i] = max(T[i * 2], T[i * 2 + 1]);
}
int Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
if (L > R || R < sL || sR < L) return -1;
if (L <= sL && sR <= R) return T[n];
int mid = (sL + sR) >> 1;
return max(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
}
int PathQuery(int a, int b) {
//printf("PQ %d %d\n", a, b);
int ret = -1;
while (R[a] != R[b]) {
if (D[R[a]] > D[R[b]]) swap(a, b);
ret = max(ret, Query(in[R[b]], in[b]));
b = P[R[b]];
}
if (D[a] > D[b]) swap(a, b);
return max(ret, Query(in[a], in[b]));
}
} T;
int main() {
int test;
cin >> test;
while (test--) {
int N, Q, no = 0;
cin >> N;
for (int i = 1; i < N; ++i) {
int a, b;
cin >> a >> b;
TG[a].push_back(b);
TG[b].push_back(a);
}
cin >> Q;
for (int i = 0; i < Q; ++i) cin >> E[i].first >> E[i].second;
dn = 0;
MakeG(1, 1);
DFS(1);
DFS2(1, 1);
memset(ind, 0, sizeof(ind));
fill(ES, ES + N, -1);
for (int i = 0; i < Q; ++i) ES[E[i].second] = i;
DFS3(1, -1);
T.Clear();
for (int i = 0; i < Q; ++i) T.Update(in[E[i].first], i);
memset(C, 0, sizeof(C));
set<int> cand;
for (int i = 0; i < Q; ++i) {
if (!ind[i]) cand.insert(i);
}
while (!cand.empty()) {
int init = *cand.begin();
//printf("Start at: %d\n", init);
vector<int> ST;
set<int> V;
ST.push_back(init); V.insert(init);
while (!ST.empty()) {
int cur = ST.back();
T.Update(in[E[cur].first], -1);
int t = T.PathQuery(E[cur].first, E[cur].second);
T.Update(in[E[cur].first], cur);
//cout << cur << ' ' << t << '\n';
//cout.flush();
if (t == 1e9 || V.find(t) != V.end() || (t != -1 && cand.find(t) == cand.end())) {
no = 1;
goto END;
}
else if (t != -1) {
ST.push_back(t); V.insert(t);
continue;
}
if (!EG[cur].empty() && !--ind[EG[cur][0]]) {
cand.insert(EG[cur][0]);
}
T.Update(in[E[cur].first], -1);
T.Update(in[E[cur].second], 1e9);
cand.erase(cur);
ST.pop_back();
}
}
END:
cout << (no ? "No" : "Yes") << '\n';
for (int i = 1; i <= N; ++i) {
G[i].clear();
TG[i].clear();
EG[i].clear();
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
jail.cpp: In function 'int DFS(int)':
jail.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < G[cur].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void DFS2(int, int)':
jail.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < G[cur].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... |