Submission #1026110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026110		happy_node	Inside information (BOI21_servers)	C++17	100 / 100	403 ms	44884 KiB

servers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=3e5+5;

int N,K;

char tp[MX];
int A[MX], B[MX];

vector<pair<int,int>> adj[MX], Q[MX];
vector<int> C[MX];

bool vis[MX];
int ans[MX], sz[MX], stk[MX];

struct fenwick {
        int t[MX];

        void upd(int v, int x) {
                for(int i=v;i<MX;i+=i&-i) t[i]+=x;
        }

        int que(int v) {
                int res=0;
                for(int i=v;i>0;i-=i&-i) res+=t[i];
                return res;
        }

        int que(int l, int r) {
                return que(r)-que(l-1);
        }
} ft;

int getSize(int v, int p) {
        sz[v]=1;
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u]) continue;
                sz[v]+=getSize(u,v);
        }
        return sz[v];
}

int getCen(int v, int p, int s) {
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u] || 2*sz[u]<=s) continue;
                return getCen(u,v,s);
        }
        return v;
}

void calc(int v, int p, int prv, int head) {
        for(auto [a,id]:Q[v]) {
                if(stk[a]!=-1 && stk[a]<=id) {
                        ans[id]=1;
                }
        }
        for(auto id:C[v]) {
                if(head>id) continue;
                ans[id]+=ft.que(head,id);
        }
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u]) continue;
                if(prv<w) continue;
                calc(u,v,w,head);
        }
}

void upd(int v, int p, int prv) {
        stk[v]=prv;
        ft.upd(prv,1);
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u]) continue;
                if(prv>w) continue;
                upd(u,v,w);
        }
}

void rem(int v, int p, int prv) {
        stk[v]=-1;
        ft.upd(prv,-1);
        for(auto [u,w]:adj[v]) {
                if(u==p || vis[u]) continue;
                if(prv>w) continue;
                rem(u,v,w);
        }
}

void cdc(int v, int p) {
        int s=getSize(v,v);
        int cen=getCen(v,v,s);

        vis[cen]=1;

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                stk[cen]=w;
                ft.upd(w,1);
                calc(u,cen,w,w);
                upd(u,cen,w);
                ft.upd(w,-1);
        }

        stk[cen]=0;

        for(auto [a,id]:Q[cen]) {
                if(stk[a]!=-1 && stk[a]<=id) {
                        ans[id]=1;
                }
        }

        for(auto id:C[cen]) {
                ans[id]+=ft.que(1,id);
        }

        stk[cen]=-1;

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                rem(u,cen,w);
        }

        for(auto [u,w]:adj[cen]) {
                if(vis[u]) continue;
                cdc(u,cen);
        }
}

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        cin>>N>>K;

        for(int i=0;i<MX;i++) stk[i]=-1;

        for(int i=1;i<N+K;i++) {
                cin>>tp[i]>>A[i];
                if(tp[i]=='S') {
                        cin>>B[i];
                        adj[A[i]].push_back({B[i],i});
                        adj[B[i]].push_back({A[i],i});
                } else if(tp[i]=='Q') {
                        cin>>B[i];
                        // B -> A path increasing
                        Q[B[i]].push_back({A[i],i});
                } else {
                        C[A[i]].push_back(i);
                }
        }

        for(int i=1;i<=N;i++) {
                sort(adj[i].begin(),adj[i].end(),[&](auto x, auto y) {
                        return x.second>y.second;
                });
        }

        cdc(1,0);

        for(int i=1;i<N+K;i++) {
                if(tp[i]=='S') continue;
                if(tp[i]=='Q') {
                        if(ans[i]) cout<<"yes\n";
                        else cout<<"no\n";
                } else {
                        cout<<ans[i]+1<<'\n';
                }
        }
}

• 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