# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
741143 | Dan4Life | Jail (JOI22_jail) | C++17 | 9 ms | 992 KiB |
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>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
const int mxN = (int)300;
const int mxM = (int)500;
const int LINF = (int)2e18;
int n, m, s[mxM], t[mxM], vis[mxM], dis[mxN][mxN];
vector<int> adj[mxN], adj2[mxN];
bool Cycle;
void dfs(int s, int p, int ro){
if(p==-1) dis[ro][s] = 0;
else dis[ro][s] = dis[ro][p]+1;
for(auto u : adj[s]){
if(u==p) continue;
dfs(u,s,ro);
}
}
bool inPath(int x, int s, int t){
return (dis[s][x]+dis[t][x]==dis[s][t]);
}
void dfs2(int s){
vis[s] = 1;
for(auto u : adj2[s]){
if(!vis[u]) dfs2(u);
else if(vis[u]==1) { Cycle=1; return; }
}
vis[s]=2;
}
void solve(){
cin >> n; Cycle = 0;
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 0; i < n-1; i++){
int a, b; cin >> a >> b;
adj[a].pb(b), adj[b].pb(a);
}
for(int i = 1; i <= n; i++) dfs(i,-1,i);
for(int i = 0; i < m; i++) vis[i]=0;
cin >> m; bool ok = 1;
for(int i = 0; i < m; i++) cin >> s[i] >> t[i];
for(int i = 0; i < m and ok; i++){
for(int j = 0; j < m and ok; j++){
if(i==j) continue;
int a = s[i], b = t[i], c = s[j], d = t[j];
if(inPath(s[j],s[i],t[i])) adj2[j].pb(i);
}
}
for(int i = 0; i < m; i++) if(!vis[i]) dfs2(i);
cout << (!Cycle?"Yes":"No") << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1; cin >> t; while(t--) solve();
}
Compilation message (stderr)
# | 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... |