Submission #812179

#	Time	Username	Problem	Language	Result	Execution time	Memory
812179		alvingogo	Inside information (BOI21_servers)	C++14	100 / 100	437 ms	33372 KiB

servers

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
    int n;
    vector<int> bt;
    void init(int x){
        n=x;
        bt.resize(n+1);
    }
    void update(int x,int y){
        x++;
        for(;x<=n;x+=(x&-x)){
            bt[x]+=y;
        }
    }
    int query(int x){
        x++;
        int ans=0;
        for(;x>0;x-=(x&-x)){
            ans+=bt[x];
        }
        return ans;
    }
}bt;

vector<int> ans;
struct no{
    vector<pair<int,int> > ch;
    int ab=0;
    int sz;
    int vis=0;
    vector<int> l;
    vector<pair<int,int> > r;
    int fa=-1;
};
vector<no> v;
void init(int x){
    v.resize(x);
}
int dfs(int r,int f,int n){
    v[r].sz=1;
    int s=-1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f){
            s=max(s,dfs(h.fs,r,n));
            v[r].sz+=v[h.fs].sz;
        }
    }
    if(s>=0){
        return s;
    }
    else if(v[r].sz>n/2){
        return r;
    }
    else{
        return -1;
    }
}
void dfs2(int r,int f){
    v[r].sz=1;
    v[r].fa=-1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f){
            dfs2(h.fs,r);
            v[r].sz+=v[h.fs].sz;
        }
    }
}
void dfs3(int r,int f,int z){
    for(auto h:v[r].l){
        ans[h]+=bt.query(h);
    }
    for(auto h:v[r].r){
        if(v[h.fs].fa>=0 && v[h.fs].fa<h.sc){
            ans[h.sc]=-2;
        }
    }
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f && h.sc<z){
            dfs3(h.fs,r,h.sc);
        }
    }
}
vector<int> g;
void dfs4(int r,int f,int z){
    g.push_back(z);
    v[r].fa=z;
    bt.update(z,1);
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f && h.sc>z){
            dfs4(h.fs,r,h.sc);
        }
    }
}
void dc(int r,int n){
    r=dfs(r,r,n);
    int m=v[r].ch.size();
    for(int i=m-1;i>=0;i--){
        auto h=v[r].ch[i];
        if(v[h.fs].vis){
            continue;
        }
        bt.update(h.sc,1);
        v[r].fa=h.sc;
        dfs3(h.fs,r,h.sc);
        dfs4(h.fs,r,h.sc);
        v[r].fa=-1;
        bt.update(h.sc,-1);
    }
    for(auto h:v[r].l){
        ans[h]+=bt.query(h)+1;
    }
    for(auto h:v[r].r){
        if(v[h.fs].fa>=0 && v[h.fs].fa<h.sc){
            ans[h.sc]=-2;
        }
    }
    while(g.size()){
        auto h=g.back();
        g.pop_back();
        bt.update(h,-1);
    }
    dfs2(r,r);
    v[r].vis=1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis){
            dc(h.fs,v[h.fs].sz);
        }
    }
}
int main(){
    AquA;
    int n,k;
    cin >> n >> k;
    int q=(n-1+k);
    vector<pair<int,pair<int,int> > > qr;
    bt.init(q+2);
    v.resize(n);
    ans.resize(q,0);
    for(int i=0;i<q;i++){
        char s;
        cin >> s;
        if(s=='S'){
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            v[a].ch.push_back({b,i});
            v[b].ch.push_back({a,i});
            ans[i]=-3;
        }
        else if(s=='Q'){
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            if(a==b){
                ans[i]=-2;
                continue;
            }
            v[b].r.push_back({a,i});
            ans[i]=-1;
        }
        else{
            int a;
            cin >> a;
            a--;
            v[a].l.push_back(i);
        }
    }
    dc(0,0);
    for(int i=0;i<q;i++){
        if(ans[i]!=-3){
            if(ans[i]<0){
                if(ans[i]==-1){
                    cout << "no\n";
                }
                else{
                    cout << "yes\n";
                }
            }
            else{
                cout << ans[i] << "\n";
            }
        }
    }
    return 0;
}

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