Submission #1026008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026008		happy_node	Inside information (BOI21_servers)	C++17	0 / 100	31 ms	18916 KiB

servers

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

typedef long long ll;

const int MX=2e5+5;

int N,K;

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

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

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

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) {
        for(auto [a,id]:Q[v]) {
                if(stk[a]!=0 && stk[a]<=id) {
                        ans[id]=1;
                }
        }
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                if(prv<w) continue;
                calc(u,v,w);
        }
}

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

void rem(int v, int p) {
        stk[v]=0;
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                rem(u,v);
        }
}

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

        vis[cen]=1;

        sort(adj[cen].begin(),adj[cen].end(),[&](auto x, auto y) {
                return x.second>y.second;
        });

        stk[cen]=1;

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

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

        stk[cen]=0;

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

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

        cdc(1,0);

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

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