Submission #1000215

#TimeUsernameProblemLanguageResultExecution timeMemory
1000215onbertJail (JOI22_jail)C++17
0 / 100
12 ms6484 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e18; int n, m; vector<int> ADJ[maxn], adj[maxn]; pair<int,int> a[maxn]; int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0; void dfs1(int u) { sz[u] = 1; int f = -1; for (int &v:ADJ[u]) { if (sz[v]) { f = v; continue; } dfs1(v); sz[u] += sz[v]; } if (f!=-1) ADJ[u].erase(find(ADJ[u].begin(), ADJ[u].end(), f)); for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]); } void dfs2(int u) { cnter++; newid[u] = cnter; for (int v:ADJ[u]) { d[cnter+1] = d[newid[u]] + 1; dfs2(v); fa[newid[v]] = newid[u]; } lim[u] = cnter; } void solve() { cin >> n; for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear(); cnter = 0; for (int i=1;i<=n-1;i++) { int u, v; cin >> u >> v; ADJ[u].push_back(v); ADJ[v].push_back(u); } fa[1] = 0, d[1] = 0; dfs1(1); dfs2(1); bool guy[n+1]; for (int i=1;i<=n;i++) guy[i] = 0; for (int i=1;i<=m;i++) a[i] = {-1, -1}; cin >> m; for (int i=1;i<=m;i++) { int s, t; cin >> s >> t; a[t] = {s, t}; guy[s] = true; } bool yes[n+1], no[n+1]; for (int cnt = 0; cnt < m; cnt++) { for (int i=1;i<=n;i++) yes[i] = (a[i].first!=-1), no[i] = 0; for (int i=1;i<=n;i++) { if (a[i].first==-1) continue; auto [u, v] = a[i]; auto [s, t] = a[i]; yes[i] = !guy[t]; no[s] = true; while (u!=v) { if (d[u] > d[v]) swap(u, v); v = fa[v]; if (v != t) no[v] = true; if (v != s) yes[i] &= (!guy[v]); } } bool ok = false; for (int i=1;i<=n;i++) if (yes[i] && !no[i]) { // cout << a[i].first << " " << a[i].second << endl; guy[i] = true; guy[a[i].first] = false; a[i] = {-1, -1}; ok = true; break; } if (!ok) {cout << "No\n"; return;} } cout << "Yes\n"; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) solve(); }

Compilation message (stderr)

jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]);
      |                  ~^~~~~~~~~~~~~~
#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...