Submission #680764

#TimeUsernameProblemLanguageResultExecution timeMemory
680764arnold518Jail (JOI22_jail)C++17
72 / 100
5060 ms418704 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; int Q, N, M; vector<int> adj[MAXN+10]; pii A[MAXN+10]; vector<int> S[MAXN+10], E[MAXN+10]; int dep[MAXN+10], par[MAXN+10]; vector<int> adj2[MAXN+10]; void dfs(int now, int bef, int d) { dep[now]=d; par[now]=bef; for(int nxt : adj[now]) { if(nxt==bef) continue; dfs(nxt, now, d+1); } } int vis[MAXN+10]; bool dfs2(int now) { vis[now]=1; for(int nxt : adj2[now]) { if(vis[nxt]==1) return true; if(vis[nxt]==0 && dfs2(nxt)) return true; } vis[now]=2; return false; } bool solve() { scanf("%d", &N); for(int i=1; i<N; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } scanf("%d", &M); for(int i=1; i<=M; i++) { scanf("%d%d", &A[i].first, &A[i].second); S[A[i].first].push_back(i); E[A[i].second].push_back(i); } dfs(1, 0, 1); for(int i=1; i<=M; i++) { int u=A[i].first, v=A[i].second; while(1) { if(dep[u]>dep[v]) swap(u, v); for(auto it : S[v]) if(it!=i) adj2[it].push_back(i); for(auto it : E[v]) if(it!=i) adj2[i].push_back(it); if(u==v) break; v=par[v]; } } for(int i=1; i<=M; i++) { if(vis[i]) continue; if(dfs2(i)) return false; } return true; } void clear() { for(int i=1; i<=N; i++) { adj[i].clear(); S[i].clear(); E[i].clear(); } for(int i=1; i<=M; i++) { adj2[i].clear(); vis[i]=0; } } int main() { scanf("%d", &Q); while(Q--) { if(solve()) printf("Yes\n"); else printf("No\n"); clear(); } }

Compilation message (stderr)

jail.cpp: In function 'bool solve()':
jail.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
jail.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
jail.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
#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...