| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 546531 |
2022-04-07T18:19:55 Z |
inksamurai |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
void slv(){
int n;
cin>>n;
vec(vi) adj(n);
bool pok=0;
rep(i,n-1){
int u,v;
cin>>u>>v;
u-=1,v-=1;
pok=pok or (u!=v-1);
adj[u].pb(v);
adj[v].pb(u);
}
assert(pok);
int m;
cin>>m;
vec(pii) rbts;
rep(i,m){
int s,t;
cin>>s>>t;
s-=1,t-=1;
rbts.pb({s,t});
}
// fill depth
vi parent(n,0),depth(n,0),tin(n,0),tout(n,0);
int tmer=0;
{
auto dfs=[&](auto self,int v,int par)->void{
tin[v]=tmer++;
for(auto u:adj[v]){
if(u==par) continue;
parent[u]=v;
depth[u]=depth[v]+1;
self(self,u,v);
}
tout[v]=tmer++;
};
dfs(dfs,0,-1);
}
// fill sparse table
vec(vi) spr(18,vi(n)),ids,iids;
ids=iids=spr;
vi d0(n),d1(n);
{
rep(j,18){
rep(v,n){
spr[j][v]=!j?parent[v]:spr[j-1][spr[j-1][v]];
}
}
int num=0;
rep(v,n){
d0[v]=num++;
}
rep(v,n){
d1[v]=num++;
}
rep(t,2){
rep(j,18){
rep(v,n){
if(!t) ids[j][v]=num++;
else iids[j][v]=num++;
}
}
}
// print(num);
}
// add corressponding edges to it's ranges
vec(vi) gph(50*n+m);
rep(v,n){
int up=spr[0][v];
gph[d0[up]].pb(ids[0][v]);
gph[d0[v]].pb(ids[0][v]);
gph[iids[0][v]].pb(d1[up]);
gph[iids[0][v]].pb(d1[v]);
}
rep(j,17){
rep(v,n){
int up=ids[j+1][v]; // next level node
gph[ids[j][v]].pb(up);
int par=ids[j][spr[j][v]]; // vertex after jump
gph[par].pb(up);
// if(v==2 and j==0) print(ids[j][v],ids[j][spr[j][v]],up);
int iup=iids[j+1][v]; // next level inversed node
gph[iup].pb(iids[j][v]);
par=iids[j][spr[j][v]]; // vertex after jump
gph[iup].pb(par);
}
}
// debug junk
{
// // 0 1 2 3 4 5 6 7
// // 8 9 10 11 12 13 14 15
// // 16 17 18 19 20 21 22 23
// rep(j,2){
// rep(v,n){
// if(j==1){
// cout<<ids[j][v]<<"\n";
// for(auto u:gph[ids[j][v]]){
// cout<<u<<" ";
// }
// cout<<"\n";
// }
// // cout<<ids[j][v]<<" ";
// }
// cout<<"\n";
// }
}
auto ancestor=[&](int u,int v)->bool{
return tin[u]<=tin[v] and tout[v]<=tout[u];
};
auto lca=[&](int s,int t)->int{
if(ancestor(s,t)) return s;
if(ancestor(t,s)) return t;
int u=t;
per(j,17){
if(!ancestor(spr[j][u],s)){
u=spr[j][u];
}
}
return spr[0][u];
};
rep(i,m){
auto [s,t]=rbts[i];
int now_id=50*n+i;
gph[now_id].pb(d0[s]);
gph[d1[t]].pb(now_id);
}
auto add_edge=[&](int v,int up,int id){
per(j,17){
int u=spr[j][v];
if(depth[u]>depth[up]){
gph[ids[j][v]].pb(id);
gph[id].pb(iids[j][v]);
v=u;
}
}
};
// for(auto u:gph[1]){
// print(u);
// }
vi ss(n,-1),tt(n,-1);
rep(i,m){
auto [s,t]=rbts[i];
ss[s]=50*n+i;
tt[t]=50*n+i;
}
rep(i,m){
auto [s,t]=rbts[i];
int anc=lca(s,t);
int now_id=50*n+i;
if(tt[s]!=-1){
// print(tt[s]);
gph[now_id].pb(tt[s]);
}
if(ss[t]!=-1){
// print(ss[t]);
gph[ss[t]].pb(now_id);
}
if(ancestor(s,t) or ancestor(t,s)){
if(ancestor(t,s)) swap(s,t);
// print("here");
t=spr[0][t];
int id=now_id,up=s;
int v=t;
if(s!=t){
// print(d0[t],id);
// print(id,d1[t]);
gph[d0[t]].pb(id);
gph[id].pb(d1[t]);
}
per(j,17){
int u=spr[j][v];
if(depth[u]>depth[up]){
// print(v,u,j,ids[j][v],id);
// print(v,u,s,t,j,ids[j+1][v],id);
gph[ids[j][v]].pb(id);
gph[id].pb(iids[j][v]);
v=u;
}
}
}else{
// print("here");
if(depth[s]-depth[anc]>=2){
s=spr[0][s];
add_edge(s,anc,now_id);
}
if(depth[t]-depth[anc]>=2){
t=spr[0][t];
add_edge(t,anc,now_id);
}
}
}
auto has_cyc=[&]()->bool{
vi usd(50*n+m,0),usd1(50*n+m,0);
bool cyc=0;
auto dfs=[&](auto self,int v)->void{
usd[v]=1;
usd1[v]=1;
// print(v);
for(auto u:gph[v]){
if(usd1[u]){
// print(u,v);
cyc=1;
}
if(!usd[u]){
self(self,u);
}
}
usd1[v]=0;
};
// dfs(dfs,0);
rep(v,50*n+m){
if(!usd[v]){
dfs(dfs,v);
}
}
return cyc;
};
int res=has_cyc();
// print(res);
print(res?"No":"Yes");
}
signed main(){
_3x2WzQf;
int t;
cin>>t;
rep(cs,t){
slv();
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
