Submission #1140436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140436		mnbvcxz123	Inside information (BOI21_servers)	C++20	100 / 100	288 ms	37248 KiB

servers

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;

#define fi first
#define se second

constexpr int N=2e5+5;
int n,q;

int aib[2*N+5];
vector<int>undo;

void update(int pos, int val){
    while(pos<n+q){
        aib[pos]+=val;
        undo.push_back(pos);
        pos+=pos&-pos;
    }
}

int query(int pos){
    int ans=0;
    while(pos){
        ans+=aib[pos];
        pos-=pos&-pos;
    }
    return ans;
}

void clear(){
    for(const int&i:undo)aib[i]=0;
    undo.clear();
}

struct Query{
    char type;
    int to,time;
};

vector<Query>qry[N+5];
vector<pi>g[N+5];
int ans[2*N+5],sz[2*N+5];
int mtp[N+5];
int crd[N+5];
int par[N+5];
int sub[N+5];
bool del[N+5];
bool nigga[N+5];

void dfssz(int v, int e){
    sz[v]=1;
    for(const auto&[i,j]:g[v])
        if(!del[i] and i!=e)
            dfssz(i,v),sz[v]+=sz[i];
}

int getcent(int v, int kutas){
    for(const auto&[i,j]:g[v])
        if(!del[i] and sz[i]<sz[v] and sz[i]>kutas)
            return getcent(i,kutas);
    return v;
}

void dfs(int v, vector<int>&x){
    x.push_back(v);
    nigga[v]=1;
    for(auto[i,j]:g[v]){
        if(del[i] or i==par[v])continue;
        par[i]=v;
        sub[i]=sub[v];
        mtp[i]=j;
        crd[i]=0;
        if(j<mtp[v] and (crd[v]&1))++crd[i];
        if(j>mtp[v] and (crd[v]&2))crd[i]+=2;
        dfs(i,x);
    }
}

void decomp(int v){
    dfssz(v,0);
    int cen=getcent(v,sz[v]>>1);
    vector<pair<int,vector<int>>>subarb;
    for(const auto&[i,j]:g[cen]){
        if(del[i])continue;
        subarb.push_back({i,{}});
        par[i]=cen;
        sub[i]=i;
        mtp[i]=j;
        crd[i]=3;
        dfs(i,subarb.back().se);
    }
    mtp[cen]=0;
    sort(subarb.begin(),subarb.end(),[&](auto a, auto b){
        return mtp[a.fi]>mtp[b.fi];
    });
    nigga[cen]=1;
    crd[cen]=3;
    update(1,1);
    for(const auto&[i,vec]:subarb){
        for(auto j:vec)
            for(auto k:qry[j]){
                if(k.type=='c'){
                    if(mtp[sub[j]]<=k.time and (crd[j]&1))
                        ans[k.time]+=query(k.time);
                }else {
                    if(k.to!=cen and nigga[k.to] and mtp[sub[k.to]]>mtp[sub[j]]
                        and mtp[k.to]<=k.time and (crd[k.to]&2) and (crd[j]&1))
                            ans[k.time]=-1;
                    else if(k.to==cen and (crd[j]&1) and mtp[sub[j]]<=k.time)
                        ans[k.time]=-1;
                }
            }
        for(auto j:vec)
            if(crd[j]&2)
                update(mtp[j],1);
    }
    update(1,-1);
    for(auto i:qry[cen]){
        if(i.type=='c')
            ans[i.time]+=query(i.time);
        else{
            if(nigga[i.to] and (crd[i.to]&2) and mtp[i.to]<=i.time)
                ans[i.time]=-1;
        }
    }
    clear();
    nigga[cen]=0;
    for(auto i:subarb)
        for(auto j:i.se)
            nigga[j]=0;
    del[cen]=1;
    for(auto[i,j]:g[cen])
        if(!del[i])
            decomp(i);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<n+q;++i){
        char t;
        cin>>t;
        if(t=='S'){
            int u,v;
            cin>>u>>v;
            g[u].push_back({v,i});
            g[v].push_back({u,i});
            ans[i]=-3;
        }else if(t=='Q'){
            int u,v;
            cin>>u>>v;
            qry[v].push_back({'q',u,i});
            ans[i]=-2;
        }else{
            int u;
            cin>>u;
            qry[u].push_back({'c',0,i});
        }
    }
    decomp(1);
    for(int i=1;i<n+q;++i){
        if(ans[i]==-1)
            cout<<"yes\n";
        else if(ans[i]==-2)
            cout<<"no\n";
        else if(ans[i]>=0)
            cout<<ans[i]+1<<'\n';
    }
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18