Submission #651788

#	Time	Username	Problem	Language	Result	Execution time	Memory
651788		victor_gao	Jail (JOI22_jail)	C++17	5 / 100	24 ms	6372 KiB

jail

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 120015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct tarjan{
    int dfn[N],low[N],dft=0,nscc=0,n;
    bool ins[N];
    stack<int>st;
    vector<int>g[N];
    void init(int _n){
        while (!st.empty()) st.pop();
        n=_n; dft=0; nscc=0;
        for (int i=0;i<=n+5;i++){
            dfn[i]=0; low[i]=0; ins[i]=0;
            g[i].clear();
        }
    }
    void addedge(int u,int v){ g[u].push_back(v); }
    void dfs(int p){
        dfn[p]=low[p]=++dft;
        st.push(p); ins[p]=1;
        for (auto i:g[p]){
            if (!dfn[i]){
                dfs(i);
                low[p]=min(low[p],low[i]);
            }
            else if (ins[i]&&dfn[i]<dfn[p])
                low[p]=min(low[p],dfn[i]);
        }
        if (low[p]==dfn[p]){
            nscc++;
            for (int x=0;x!=p;st.pop()){
                x=st.top(); ins[x]=0;
            }
        }
    }
    int solve(){
        for (int i=1;i<=n;i++){
            if (!dfn[i]) dfs(i);
        }
        return nscc;
    }
}topo;
int n,m,st[N],ed[N],son[N],cnt[N],insub[N],fd[N],fs[N];
bool vis[N];
vector<int>g[N],path,start,vend,all;
int get_size(int p,int lp){
    son[p]=1;
    insub[st[p]]++; insub[ed[p]]++;
    fd[st[p]]=0; fs[st[p]]=0;
    fd[ed[p]]=0; fs[ed[p]]=0;
    all.push_back(p);
    for (auto i:g[p]){
        if (i!=lp&&!vis[i]) son[p]+=get_size(i,p);
    }
    return son[p];
}
int get_centroid(int p,int lp,int sz){
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp&&son[i]>sz/2)
            return get_centroid(i,p,sz);
    }
    return p;
}
void same_sub(int p,int lp){
    if (st[p]) cnt[st[p]]++;
    if (ed[p]) cnt[ed[p]]++;
    path.push_back(p);
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp) same_sub(i,p);
    }
}
void build(int p,int lp){
    // 結束點先放
    if (ed[p]){
        //cout<<"add : "<<ed[p]<<'\n';
        if (cnt[ed[p]]==1&&insub[ed[p]]==2){
            for (int i=vend.size()-1;i>=0;i--){
                topo.addedge(ed[p],vend[i]);
                i=fd[vend[i]];
                fd[ed[p]]=i;
            }
            for (int i=start.size()-1;i>=0;i--){
                topo.addedge(start[i],ed[p]);
                i=fd[start[i]];
            }
        }
        vend.push_back(ed[p]);
    }
    if (st[p]){
      //  cout<<"add : "<<st[p]<<'\n';
        if (cnt[st[p]]==1&&insub[st[p]]==2){
            for (int i=vend.size()-1;i>=0;i--){
                topo.addedge(st[p],vend[i]);
                i=fd[vend[i]];
            }
            for (int i=start.size()-1;i>=0;i--){
                topo.addedge(start[i],st[p]);
                i=fs[start[i]];
                fs[st[p]]=i;
            }
        }
        start.push_back(st[p]);
    }
    for (auto i:g[p]){
        if (!vis[i]&&i!=lp) build(i,p);
    }
    if (ed[p]) vend.pop_back();
    if (st[p]) start.pop_back();
}
void reset_path(){
    for (auto i:path){
        cnt[st[i]]=0;
        cnt[ed[i]]=0;
    }
    path.clear();
}
void decompose(int p,int lp){
    int sz=get_size(p,lp);
    int mid=get_centroid(p,lp,sz);
   // cout<<p<<" "<<lp<<" -> "<<mid<<' '<<sz<<'\n';
    vis[mid]=1;
    start.clear(); vend.clear();
    if (ed[mid]){
        vend.push_back(ed[mid]);
    } 
    if (st[mid]){
        if (!vend.empty()) topo.addedge(st[mid],vend.back());
        start.push_back(st[mid]);
    } 
    for (auto i:g[mid]){
        if (!vis[i]&&i!=lp){
            same_sub(i,mid);
            build(i,mid);
            reset_path();
        }
    }
    for (auto i:all){
        insub[st[i]]=0; insub[ed[i]]=0;
        cnt[st[i]]=0; cnt[ed[i]]=0;
    }
    all.clear();
    /*
    cout<<"after : \n";
    for (int i=1;i<=m;i++){
        cout<<i<<" -> ";
        for (auto j:topo.g[i])
            cout<<j<<" ";
        cout<<'\n';
    }
    cout<<"\n";
    */
    for (auto i:g[mid]){
        if (!vis[i]&&i!=lp)
            decompose(i,mid);
    }
}
void reset(int n){
    start.clear(); vend.clear(); path.clear();
    for (int i=0;i<=n+5;i++){
        g[i].clear();
        st[i]=0; ed[i]=0; vis[i]=0;
        son[i]=0; cnt[i]=0;
    }
}
signed main(){
    fast
    int t; cin>>t;
    while (t--){
        cin>>n;
        reset(n);
        for (int i=1;i<n;i++){
            int a,b; cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cin>>m;
        for (int i=1;i<=m;i++){
            int a,b; cin>>a>>b;
            st[a]=i; ed[b]=i;
        }
        topo.init(m);
        decompose(1,0);
        /*
        for (int i=1;i<=m;i++){
            cout<<i<<" -> ";
            for (auto j:topo.g[i])
                cout<<j<<" ";
            cout<<'\n';
        }
        */
        int ans=topo.solve();
        if (ans==m) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

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