Submission #1127343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127343		imarn	Inside information (BOI21_servers)	C++20	96 / 96	527 ms	52668 KiB

servers

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define t3 tuple<int,int,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=120050;
vector<pii>g[mxn];
struct fenwick{
    vector<int>vec,fw;
    void build(){
        sort(vec.begin(),vec.end());
        fw.resize(vec.size()+1,0);
    }
    void upd(int i,int amt){
        i=upper_bound(all(vec),i)-vec.begin();
        for(;i<fw.size();i+=i&-i)fw[i]+=amt;
    }
    int qr(int i,int rs=0){
        i=upper_bound(all(vec),i)-vec.begin();
        for(;i;i-=i&-i)rs+=fw[i];
        return rs;
    }
}fen[mxn];
int pr[mxn]{0},lv[mxn]{0},f[mxn]{0},id[20][mxn]{0},tin[20][mxn]{0};
int cur[20]{0};
int sz[mxn]{0};
bool vis[mxn]{0};
bool conn[2][20][mxn]{0};
int get(int r){
    return f[r]==r?r:f[r]=get(f[r]);
}
int getsz(int u,int p){
    sz[u]=1;
    for(auto [v,w]:g[u]){
        if(v==p||vis[v])continue;
        sz[u]+=getsz(v,u);
    }return sz[u];
}
int getct(int u,int p,int re){
    for(auto [v,w]:g[u]){
        if(v==p||vis[v])continue;
        if(sz[v]*2>re)return getct(v,u,re);
    }return u;
}
void dfs1(int u,int p,int ct,int mn1,int mn2,int ww,int d){
    tin[lv[ct]][u]=++cur[lv[ct]];
    for(auto [v,w]:g[u]){
        if(vis[v]||v==p)continue;
        dfs1(v,u,ct,min(mn1,w-d),min(mn2,d-w),ww,w);
    }
    if(mn1>=0)conn[0][lv[ct]][u]=1;
    if(mn2>=0)conn[1][lv[ct]][u]=1;
    id[lv[ct]][u]=ww;
}
void play(int u,int p){
    int x=getct(u,u,getsz(u,u));
    vis[x]=1;pr[x]=p;
    if(p!=-1)lv[x]=lv[p]+1;
    tin[lv[x]][x]=++cur[lv[x]];
    conn[0][lv[x]][x]=1;
    conn[1][lv[x]][x]=1;
    id[lv[x]][x]=0;fen[x].vec.pb(0);
    for(auto [v,w]:g[x]){
        if(vis[v])continue;
        dfs1(v,x,x,0,0,w,w);
        fen[x].vec.pb(w);
    }fen[x].build();
    for(auto [v,w]:g[x]){
        if(vis[v])continue;
        play(v,x);
    }
}
int getlct(int x,int y){
    while(x!=y){
        if(lv[x]<lv[y])y=pr[y];
        else x=pr[x];
    }return x;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    vector<t3>qr;iota(f,f+n+1,0);
    for(int i=0;i<n+k-1;i++){
        char s;cin>>s;
        if(s=='S'){int a,b;cin>>a>>b;qr.pb({0,a,b});}
        if(s=='Q'){int a,b;cin>>a>>b;qr.pb({1,a,b});}
        if(s=='C'){int a;cin>>a;qr.pb({2,a,0});}
    }int cu=0;
    for(auto [o,u,v]:qr){
        if(o)continue;
        g[u].pb({v,++cu});
        g[v].pb({u,cu});
    }play(1,-1);
    for(auto [o,u,v]:qr){
        if(o==0){
            f[get(u)]=get(v);
            int lct=getlct(u,v);
            while(lct!=-1){
                if(tin[lv[lct]][u]<tin[lv[lct]][v]&&conn[0][lv[lct]][v])fen[lct].upd(id[lv[lct]][v],1);
                else if(tin[lv[lct]][u]>tin[lv[lct]][v]&&conn[0][lv[lct]][u])fen[lct].upd(id[lv[lct]][u],1);
                lct=pr[lct];
            }

        }
        if(o==1){bool ok=1;
            if(get(u)!=get(v))ok=0;
            int x=getlct(u,v);
            if(!(conn[0][lv[x]][u]&&conn[1][lv[x]][v]&&(id[lv[x]][u]>=id[lv[x]][v]||x==v||x==u)))ok=0;
            cout<<(ok?"yes\n":"no\n");
        }
        if(o==2){
            int rs=0;
            int x=u;
            while(x!=-1){
                if(get(x)!=get(u)){x=pr[x];continue;}
                if(conn[1][lv[x]][u])rs+=fen[x].qr(1e9)-fen[x].qr(id[lv[x]][u])+1;
                x=pr[x];
            }cout<<rs<<'\n';
        }
    };
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 2 / 2
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12
• Subtask 11: 17 / 17
• Subtask 12: 17 / 17