Submission #575605

#TimeUsernameProblemLanguageResultExecution timeMemory
575605InternetPerson10Jail (JOI22_jail)C++17
0 / 100
2 ms332 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; vector<vector<int>> adj; vector<bool> taken; vector<vector<int>> val; vector<vector<int>> paths; vector<vector<int>> adjm; vector<int> inDeg; bool dfs(int n, int tar) { taken[n] = true; if(n == tar) { paths.back().push_back(n); return true; } for(int ch : adj[n]) { if(taken[ch]) continue; if(dfs(ch, tar)) { paths.back().push_back(n); return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; adj.resize(n); taken.resize(n); for(int i = 1; i < n; i++) { int x, y; cin >> x >> y; x--; y--; adj[x].push_back(y); adj[y].push_back(x); } int m; cin >> m; val.resize(n, vector<int>()); adjm.resize(m, vector<int>()); inDeg.resize(m); for(int i = 0; i < m; i++) { paths.push_back(vector<int>()); int x, y; cin >> x >> y; dfs(x-1, y-1); for(int j = 0; j < n; j++) { taken[j] = false; } reverse(paths[i].begin(), paths[i].end()); val[paths[i].front()].push_back(i+1); val[paths[i].back()].push_back(-(i+1)); } for(int i = 0; i < m; i++) { for(int g : paths[i]) { for(int z : val[g]) { int x = i; int y = abs(z) - 1; if(x == y) continue; if(g == paths[i].back()) swap(x, y); adjm[x].push_back(y); inDeg[y]++; } } } queue<int> q; int movedP = 0; for(int i = 0; i < m; i++) { if(inDeg[i] == 0) q.push(i); } while(q.size()) { movedP++; int g = q.front(); q.pop(); for(int k : adjm[g]) { inDeg[k]--; if(inDeg[k] == 0) { q.push(k); } } } bool ok = (movedP == m); cout << (ok ? "Yes\n" : "No\n"); val.clear(); adj.clear(); paths.clear(); taken.clear(); adjm.clear(); inDeg.clear(); } }
#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...