제출 #781383

#제출 시각아이디문제언어결과실행 시간메모리
781383IBoryJail (JOI22_jail)C++17
5 / 100
251 ms45404 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...