Submission #553021

#TimeUsernameProblemLanguageResultExecution timeMemory
553021tht2005Jail (JOI22_jail)C++17
61 / 100
5022 ms33124 KiB
#include <bits/stdc++.h> using namespace std; const int N = 120005; int n, m, cnt, s[N], t[N], in[N]; vector<int> aj[N], ej[N], S[N], T[N]; queue<int> q; bool dfs(int v, int p_, int t, int i) { bool ok = (v == t); for(int u : aj[v]) { if(ok) break; if(u == p_) continue; ok |= dfs(u, v, t, i); } if(ok) { for(int j : S[v]) { if(i != j) { ej[j].push_back(i); } } for(int j : T[v]) { if(i != j) { ej[i].push_back(j); } } } return ok; } int main() { int _; scanf("%d", &_); while(_--) { scanf("%d", &n); for(int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); aj[u].push_back(v); aj[v].push_back(u); } scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%d %d", s + i, t + i); S[s[i]].push_back(i); T[t[i]].push_back(i); } for(int i = 1; i <= m; ++i) { dfs(s[i], -1, t[i], i); } for(int i = 1; i <= m; ++i) { for(int j : ej[i]) { ++in[j]; } } for(int i = 1; i <= m; ++i) { if(in[i] == 0) { q.push(i); } } cnt = 0; while(!q.empty()) { int v = q.front(); q.pop(); ++cnt; for(int u : ej[v]) { if((--in[u]) == 0) { q.push(u); } } } for(int i = 1; i <= n; ++i) { aj[i].clear(); ej[i].clear(); S[i].clear(); T[i].clear(); in[i] = 0; } puts((cnt == m) ? "Yes" : "No"); } return 0; }

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &_);
      |     ~~~~~^~~~~~~~~~
jail.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
jail.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |             scanf("%d %d", s + i, t + 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...