This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int inf = 1e18;
vector<vector<int>> g;
vector<vector<int>> h;
vector<int> start, endd;
void merge(vector<int>& A, vector<int>& B){
if(A.size() < B.size())swap(A, B);
for(auto e : B)A.pb(e);
}
void dfs1(int u, int p, vector<int>& bef, vector<int>& aft){
for(auto v : g[u]){
if(v == p)continue;
vector<int> tmp1, tmp2;
dfs1(v, u, tmp1, tmp2);
merge(bef, tmp1);
merge(aft, tmp2);
}
if(start[u] != -1){
for(auto& e : bef)h[e].pb(start[u]);
bef.clear();
}
if(endd[u] != -1){
for(auto& e : aft)h[endd[u]].pb(e);
aft.clear();
}
if(start[u] != -1){
bef.pb(start[u]);
aft.pb(start[u]);
}
if(endd[u] != -1){
bef.pb(endd[u]);
aft.pb(endd[u]);
}
if(start[u] != -1 && endd[u] != -1){
h[endd[u]].pb(start[u]);
}
}
int dfs2(int u, vector<int>& col){
if(col[u] == 2)return 1;
if(col[u] == 1)return 0;
col[u] = 1;
int ret = 1;
for(auto v : h[u]){
ret = min(ret, dfs2(v, col));
}
col[u] = 2;
return ret;
}
void solve(){
int n; cin >> n;
g.assign(n, vector<int>());
for(int i = 0; i< n; i++){
int c, d; cin >> c >> d; c--; d--;
g[c].pb(d);
g[d].pb(c);
}
int m; cin >> m;
start.assign(n, -1);
endd.assign(n, -1);
h.assign(m, vector<int>());
for(int i = 0; i< m; i++){
int c, d; cin >> c >> d; c--; d--;
start[c] = i;
endd[d] = i;
}
vector<int> tmp1, tmp2;
dfs1(0, 0, tmp1, tmp2);
int ans = 1;
vector<int> col(m);
for(int i = 0; i< m; i++)ans = min(ans, dfs2(i, col));
if(ans)cout << "Yes\n";
else cout << "No\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
cin >> t;
while(t--)solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |