Submission #1204019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204019		Unforgettablepl	Inside information (BOI21_servers)	C++20	48 / 100	153 ms	47348 KiB

servers

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,K;
    cin >> N >> K;
    vector<int> depth(N+1);
    vector lift(N+1,vector(17,0ll));
    vector<int> maxup(N+1);
    vector<int> maxdown(N+1);
    vector<int> pEdge(N+1);
    vector<tuple<int,int,int>> queries;
    vector<vector<pair<int,int>>> adj(N+1);
    {
        int tim = 0;
        for(int i=1;i<=N-1+K;i++){
            char t;cin>>t;
            if(t=='S'){
                int a,b;
                cin >> a >> b;
                tim++;
                adj[a].emplace_back(b,tim);
                adj[b].emplace_back(a,tim);
            } else if(t=='Q'){
                int a,d;
                cin >> a >> d;
                queries.emplace_back(tim,a,d);
            } else {
                int d;
                cin >> d;
                queries.emplace_back(tim,-1,d);
            }
        }
    }
    {
        function<void(int,int)> dfs = [&](int x,int p){
            lift[x][0]=p;
            depth[x]=depth[p]+1;
            maxup[x]=depth[x]-1;
            if(pEdge[p]>pEdge[x])maxup[x]=maxup[p];
            maxdown[x]=depth[x]-1;
            if(pEdge[p]<pEdge[x])maxdown[x]=maxdown[p];
            for(auto&[i,cost]:adj[x])if(i!=p){
                pEdge[i]=cost;
                dfs(i,x);
            }
        };
        dfs(1,0);
        for(int bit=1;bit<17;bit++){
            for(int i=1;i<=N;i++){
                lift[i][bit]=lift[lift[i][bit-1]][bit-1];
            }
        }
    }
    auto lcas = [&](int a,int b){
        if(depth[b]<depth[a])swap(a,b);
        int target = depth[b]-depth[a];
        for(int bit=0;bit<17;bit++)if(target&(1<<bit))b=lift[b][bit];
        if(a==b)return a;
        for(int bit=16;bit>=0;bit--)if(lift[a][bit]!=lift[b][bit]){
            a = lift[a][bit];
            b = lift[b][bit];
        }
        return lift[a][0];
    };
    for(auto&[tim,a,b]:queries){
        if(a==-1){
            // Count how many servers have b
        } else {
            int lca = lcas(a,b);
            swap(a,b);
            int aRaised = a;
            int target = max(0ll,depth[a]-depth[lca]-1);
            for(int bit=0;bit<17;bit++)if(target&(1<<bit))aRaised=lift[aRaised][bit];
            int bRaised = b;
            target = max(0ll,depth[b]-depth[lca]-1);
            for(int bit=0;bit<17;bit++)if(target&(1<<bit))bRaised=lift[bRaised][bit];
            if(depth[lca]<maxup[a]){
                cout << "no\n";
                continue;
            }
            if(depth[lca]<maxdown[b]){
                cout << "no\n";
                continue;
            }
            if(depth[lca]!=depth[b] and depth[lca]!=depth[a] and pEdge[bRaised]<pEdge[aRaised]){
                cout << "no\n";
                continue;
            }
            if(depth[lca]!=depth[b]){
                if(pEdge[b]>tim){
                    cout << "no\n";
                }else{
                    cout << "yes\n";
                }
                continue;
            }
            if(depth[lca]==depth[b] and depth[lca]!=depth[a]){
                if(pEdge[aRaised]>tim){
                    cout << "no\n";
                }else{
                    cout << "yes\n";
                }
                continue;
            }
            cout << "yes\n";        
        }
    }
}

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