Submission #874674

#	Time	Username	Problem	Language	Result	Execution time	Memory
874674		winter0101	Jail (JOI22_jail)	C++14	100 / 100	776 ms	115096 KiB

jail

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+2e4+9;
/*
nhan xet: neu co the chuyen duoc thi ta co the chuyen tung thang 1
chung minh: dat day a voi a[i] la thang thu i di chuyen tu dau den dau
xet 1 doan l r voi a[l]=a[r] va a[l]->a[r-1] doi mot khac nhau
ta se chung minh giam duoc do dai doan l r di 1
goi thang x la thang trong thao tac a[l] va a[r]
gia su trong thao tac a[l] thang x di tu dinh v1 den v2, a[r] tu v2 den v3
nhan xet la cac thao tac tu l+1 den r-1 khong di qua dinh v2
nen ta co the goi 3 tap nhu sau la p la tap cac thao tac di chuyen trong tplt cua v1,q trong tplt cua v3, r la con lai
sau khi bo dinh v2
p,q,r la lay tu trong l+1 den r-1
nhan xet ta co the viet lai cac thao tac la q a[l] a[r] p r va co the gop a[l] voi a[r] thanh mot va ta co the giam dan ve dung m lan
=>dpcm
*/
vector<int>a[maxn];
pii b[maxn];
int sub[maxn];
int d[maxn],p[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
if (v==par)continue;
d[v]=d[u]+1;
p[v]=u;
dfs(v,u);
sub[u]+=sub[v];
if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(a[u][0],v);
}
}
int pos[maxn],h[maxn],tle=0,rev[maxn];
void hld(int u,int par,int head){
pos[u]=++tle;
h[u]=head;
if (a[u][0]!=par){
hld(a[u][0],u,head);
}
for (auto v:a[u]){
    if (v==par||v==a[u][0])continue;
    hld(v,u,v);
}
}
vector<int>g[maxn*9];//two segtree and m
bool fl=1;
int low[maxn*9],num[maxn*9],tme=0;
int n,m;
void build(int id,int l,int r){
if (l==r){
rev[l]=id;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
g[id].pb(id*2);
g[id].pb(id*2+1);
g[id*2+4*n].pb(id+4*n);
g[id*2+1+4*n].pb(id+4*n);
}
void addedg(int id,int l,int r,int u,int v,int ver){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
g[ver+8*n].pb(id);
g[id+4*n].pb(ver+8*n);
return;
}
int mid=(l+r)/2;
addedg(id*2,l,mid,u,v,ver);
addedg(id*2+1,mid+1,r,u,v,ver);
}
void takepath(int id,int u,int v){
bool f1=1,f2=1;
while (h[u]!=h[v]){
if (d[h[u]]<d[h[v]]){
swap(f1,f2);
swap(u,v);
}
addedg(1,1,n,pos[h[u]],pos[u]-f1,id);
f1=0;
u=p[h[u]];
}
if (pos[u]>pos[v]){
swap(u,v);
swap(f1,f2);
}
addedg(1,1,n,pos[u]+f1,pos[v]-f2,id);
}
stack<int>t;
void redfs(int u){
t.push(u);
low[u]=num[u]=++tme;
for (auto v:g[u]){
if (num[v]==-1)continue;
if (num[v])low[u]=min(low[u],low[v]);
else {
    redfs(v);
    low[u]=min(low[u],low[v]);
}
}
if (low[u]==num[u]){
    int dem=0;
    while (!t.empty()&&t.top()!=u){
    num[t.top()]=-1;
    dem+=(t.top()>8*n);
    t.pop();
    }
    dem+=(u>8*n);
    if (dem>1)fl=0;
    num[u]=-1;
    t.pop();
}
}
int t1[maxn];
void solve(){
    cin>>n;
    for1(i,1,n){
    a[i].clear();
    t1[i]=0;
    }
    for1(i,1,9*n){
    g[i].clear();
    num[i]=low[i]=0;
    }
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    tle=0;
    hld(1,0,1);
    build(1,1,n);
    cin>>m;
    for1(i,1,m){
    cin>>b[i].fi>>b[i].se;
    g[i+8*n].pb(rev[pos[b[i].fi]]+4*n);
    g[rev[pos[b[i].se]]].pb(i+8*n);
    t1[b[i].se]=i;
    takepath(i,b[i].fi,b[i].se);
    }
    for1(i,1,m){
    if (t1[b[i].fi]){
    g[i+8*n].pb(t1[b[i].fi]+8*n);
    }
    }
    tme=0;
    fl=1;
    for1(i,1,8*n+m)if (!num[i])redfs(i);
    if (fl)cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int test=1;
    cin>>test;
    while (test--)solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23