Submission #1193681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193681		lambd47	Inside information (BOI21_servers)	C++20	0 / 100	13 ms	5560 KiB

servers

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

#define sz(a) ((int) (a).size())

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int lg=20;

void solve() {
    vector<array<int,3>> qrs;
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);
    vector<int> dp(n,1);
    vector<int> resp(n+m);
    vector<int> edge(n+m,-1);
    L(i,0,n+m-2){
        char c;int a;
        cin>>c>>a;
        a--;
        if(c=='S'){
            int b;cin>>b;b--;
            adj[a].push_back(i);
            adj[b].push_back(i);
            edge[i]=a^b;
            qrs.push_back({0,a,b});
        }
        else if(c=='Q'){
            int b;cin>>b;
            b--;
            qrs.push_back({1,a,b});
        }
        else{
            qrs.push_back({2,a,-1});
        }
    }
    /*
    vector<vector<int>> pula(n,vector<int> (lg));
    vector<vector<bool>> sobe(n,vector<bool> (lg));
    vector<vector<bool>> desce(n,vector<bool>(lg));
    vector<vector<int>> lst(n,vector<int> (lg));
    vector<int> pai(n);

    auto dfs=[&](auto&& self, int node,int p)->void{
        pula[node][0]=p;
        sobe[node][0]=desce[node][0]=1;
        for(auto e: adj[node]){
            int vai=edge[e]^node;
            if(vai==p)continue;
            lst[vai][0]=e;
            pai[vai]=e;
            self(self,vai,node);
        }
        L(i,1,lg-1){
            pula[node][i]=pula[pula[node][i-1]][i-1];
            lst[node][i]=lst[pula[node][i-1]][i-1];
            desce[node][i]=desce[node][i-1]&&
                desce[pula[node][i-1]][i-1]&&
                (lst[node][i-1]>pai[pula[node][i-1]]);
            sobe[node][i]=sobe[node][i-1]&&
                sobe[pula[node][i-1]][i-1]&&
                (lst[node][i-1]<pai[pula[node][i-1]]);
        }
    };
    dfs(dfs,0,0);
    */

    R(i,n+m-2,0){
        auto [tp,a,b]=qrs[i];
        if(tp==0){
            int x=dp[a];
            dp[a]+=dp[b];
            dp[b]+=x;
        }
        if(tp==2){
            resp[i]=dp[a];
        }
    }
    L(i,0,n+m-2){
        auto [tp,a,b]=qrs[i];
        if(tp==2){
            resp[i]=dp[a]-resp[i]+1;
        }
    }
    L(i,0,n+m-2){
        auto [tp,a,b]=qrs[i];
        if(tp==1){
            cout<<((resp[i]==0)?"no\n":"yes\n");
        }
        if(tp==2){
            cout<<resp[i]<<"\n";
        }
    }


}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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