제출 #604143

#제출 시각아이디문제언어결과실행 시간메모리
604143SamAndJail (JOI22_jail)C++17
0 / 100
30 ms46480 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 150005; int n; vector<int> g[N]; int p0[N]; int q[N]; void dfs0(int x, int p) { p0[x] = p; q[x] = 1; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) continue; dfs0(h, x); q[x] += q[h]; } for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) { swap(g[x][i], g[x].back()); g[x].pop_back(); break; } } for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (q[h] > q[g[x][0]]) swap(g[x][i], g[x][0]); } } int tin[N], tout[N], ti; int f[N]; void dfs1(int x) { tin[x] = ++ti; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (i == 0) { f[h] = f[x]; dfs1(h); } else { f[h] = h; dfs1(h); } } tout[x] = ti; } bool c[N]; int t[N * 4]; set<int> st[N * 4]; void ubd(int tl, int tr, int x, int y, int pos) { if (tl == tr) { if (y > 0) { st[pos].insert(y); } else { y *= -1; assert(st[pos].find(y) != st[pos].end()); st[pos].erase(y); } if (st[pos].empty()) t[pos] = 0; else t[pos] = *st[pos].begin(); return; } int m = (tl + tr) / 2; if (x <= m) ubd(tl, m, x, y, pos * 2); else ubd(m + 1, tr, x, y, pos * 2 + 1); t[pos] = max(t[pos * 2], t[pos * 2 + 1]); } int qry(int tl, int tr, int l, int r, int pos) { if (l > r) return 0; if (tl == l && tr == r) return t[pos]; int m = (tl + tr) / 2; return max(qry(tl, m, l, min(m, r), pos * 2), qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)); } int qryy(int x, int y) { while (f[x] != f[y]) { if (tin[f[x]] < tin[f[y]]) swap(x, y); int ans = qry(1, n, tin[f[x]], tin[x], 1); if (ans) return ans; x = p0[f[x]]; } if (tin[x] < tin[y]) swap(x, y); return qry(1, n, tin[y], tin[x], 1); } vector<int> t2[N * 4]; void ubd2(int tl, int tr, int l, int r, int y, int pos) { if (l > r) return; if (tl == l && tr == r) { if (y > 0) t2[pos].push_back(y); else { assert(false); y *= -1; assert(!t2[pos].empty()); assert(t2[pos].back() == y); t2[pos].pop_back(); } return; } int m = (tl + tr) / 2; ubd2(tl, m, l, min(m, r), y, pos * 2); ubd2(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1); } void ubdd2(int x, int y, int z) { while (f[x] != f[y]) { if (tin[f[x]] < tin[f[y]]) swap(x, y); ubd2(1, n, tin[f[x]], tin[x], z, 1); x = p0[f[x]]; } if (tin[x] < tin[y]) swap(x, y); return ubd2(1, n, tin[y], tin[x], z, 1); } int qry2(int tl, int tr, int x, int pos) { while (!t2[pos].empty() && c[t2[pos].back()]) t2[pos].pop_back(); if (tl == tr) { if (!t2[pos].empty()) return t2[pos].back(); return 0; } int m = (tl + tr) / 2; if (!t2[pos].empty()) { if (x <= m) return max(t2[pos].back(), qry2(tl, m, x, pos * 2)); return max(t2[pos].back(), qry2(m + 1, tr, x, pos * 2 + 1)); } if (x <= m) return qry2(tl, m, x, pos * 2); return qry2(m + 1, tr, x, pos * 2 + 1); } int m; pair<int, int> b[N]; vector<int> v; void dfs(int i) { c[i] = true; ubd(1, n, tin[b[i].fi], -i, 1); while (1) { int h = qryy(b[i].fi, b[i].se); if (!h) break; dfs(h); } while (1) { int h = qry2(1, n, tin[b[i].se], 1); if (!h) break; dfs(h); } v.push_back(i); } int s[N * 4]; void ubds(int tl, int tr, int x, int y, int pos) { if (tl == tr) { s[pos] += y; return; } int m = (tl + tr) / 2; if (x <= m) ubds(tl, m, x, y, pos * 2); else ubds(m + 1, tr, x, y, pos * 2 + 1); s[pos] = s[pos * 2] + s[pos * 2 + 1]; } int qrys(int tl, int tr, int l, int r, int pos) { if (l > r) return 0; if (tl == l && tr == r) return s[pos]; int m = (tl + tr) / 2; return (qrys(tl, m, l, min(m, r), pos * 2) + qrys(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)); } int qryys(int x, int y) { int ans = 0; while (f[x] != f[y]) { if (tin[f[x]] < tin[f[y]]) swap(x, y); ans += qrys(1, n, tin[f[x]], tin[x], 1); x = p0[f[x]]; } if (tin[x] < tin[y]) swap(x, y); ans += qrys(1, n, tin[y], tin[x], 1); return ans; } void solv() { cin >> n; for (int i = 1; i <= n; ++i) { g[i].clear(); } for (int i = 0; i < n - 1; ++i) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs0(1, 1); ti = 0; f[1] = 1; dfs1(1); cin >> m; for (int i = 1; i <= m; ++i) cin >> b[i].fi >> b[i].se; for (int i = 1; i <= m; ++i) c[i] = false; for (int i = 1; i <= m; ++i) { ubd(1, n, tin[b[i].fi], i, 1); ubdd2(b[i].fi, b[i].se, i); } v.clear(); for (int i = 1; i <= m; ++i) { if (c[i]) continue; dfs(i); } for (int i = 1; i <= m; ++i) ubds(1, n, tin[b[i].fi], 1, 1); for (int ii = 0; ii < sz(v); ++ii) { int i = v[ii]; ubds(1, n, tin[b[i].fi], -1, 1); if (qryys(b[i].fi, b[i].se)) { for (int jj = ii + 1; jj < sz(v); ++jj) { int i = v[jj]; ubds(1, n, tin[b[i].fi], -1, 1); } cout << "No\n"; return; } } cout << "Yes\n"; } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; cin >> tt; while (tt--) { solv(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void dfs0(int, int)':
jail.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < g[x].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...