Submission #1039603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039603		Plurm	Inside information (BOI21_servers)	C++11	2.50 / 100	3564 ms	56252 KiB

servers

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

vector<int> g[500005];
vector<int> rg[500005];
int cnt[500005];
int primpar[500005];
int par[500005][20];
int st[500005];
int ed[500005];
int dep[500005];
int t;
void dfs(int u, int p = 0){
    par[u][0] = p;
    dep[u] = dep[p] + 1;
    st[u] = ++t;
    for(int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : rg[u]){
        dfs(v, u);
    }
    ed[u] = t;
}
int FT[500005];
void add(int idx, int amt){
    while(idx < 500005){
        FT[idx] += amt;
        idx += idx & -idx;
    }
}
int sum(int idx){
    int ret = 0;
    while(idx > 0){
        ret += FT[idx];
        idx -= idx & -idx;
    }
    return ret;
}
int lca(int u, int v){
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i--){
        if(dep[u] <= dep[par[v][i]]) v = par[v][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
bool search(int a, int d){
    return lca(a, primpar[d]) == primpar[d];
}
int count(int d){
    return sum(ed[primpar[d]]) - sum(st[primpar[d]]-1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    k += n-1;
    vector<tuple<int,int,int>> cmds;
    vector<int> ids(n+1);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
    }
    int last = n;
    for(int i = 0; i < k; i++){
        string cmd;
        cin >> cmd;
        int a, b, d;
        switch(cmd[0]){
            case 'S':
                cin >> a >> b;
                last++;
                if(ids[a] != a){
                    g[last].push_back(ids[a]);
                    rg[ids[a]].push_back(last);
                }else{
                    primpar[a] = last;
                }
                if(ids[b] != b){
                    g[last].push_back(ids[b]);
                    rg[ids[b]].push_back(last);
                }else{
                    primpar[b] = last;
                }
                ids[a] = ids[b] = last;
                cmds.push_back({0, a, b});
                break;
            case 'Q':
                cin >> a >> d;
                cmds.push_back({1, a, d});
                break;
            case 'C':
                cin >> d;
                cmds.push_back({2, d, 0});
                break;
        }
    }
    dfs(n+1);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        cnt[i]++;
    }
    last = n;
    for(int i = 0; i < k; i++){
        int a, b, d;
        switch(get<0>(cmds[i])){
            case 0:
                a = get<1>(cmds[i]);
                b = get<2>(cmds[i]);
                cnt[ids[a]]--;
                if(a != ids[a])
                    add(st[ids[a]], -1);
                cnt[ids[b]]--;
                if(b != ids[b])
                    add(st[ids[b]], -1);
                last++;
                ids[a] = ids[b] = last;
                cnt[last] += 2;
                add(st[last], 2);
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes" << endl;
                else cout << "no" << endl;
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << endl;
                break;
        }
    }
    return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 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