Submission #1040519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040519		Plurm	Inside information (BOI21_servers)	C++11	52.50 / 100	3603 ms	83076 KiB

servers

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

vector<int> g[500005];
vector<int> rg[500005];
int par[500005][20];
int dep[500005];
int ddep[500005];
int t;
void dfs(int u, int p = 0, int d = 0){
    ddep[u] = d;
    par[u][0] = p;
    dep[u] = dep[p]+1;
    for(int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u, d+1);
    }
    for(int v : rg[u]){
        if(v == p) continue;
        dfs(v, u, d-1);
    }
}
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){
    int l = lca(a, d);
    int dist = dep[a] + dep[d] - 2*dep[l];
    int ddist = ddep[d] - ddep[a];
    return dist == ddist;
}
vector<pair<int,int>> buffer;
const int THRESH = 100;
int qs[500005];
int evp[500005];
int update(int u, int p = 0, int d = 0){
    for(int v : rg[u]){
        if(v == p) continue;
        d += update(v, u, 0);
    }
    d += evp[u];
    qs[u] += d;
    for(int v : g[u]){
        if(v == p) continue;
        update(v, u, d);
    }
    return d;
}
int count(int d){
    if(buffer.size() >= THRESH){
        memset(evp, 0, sizeof(evp));
        for(auto p : buffer) evp[p.first] += p.second;
        update(1);
        buffer.clear();
    }
    int ret = qs[d];
    for(auto p : buffer){
        if(search(p.first, d)){
            ret += p.second;
        }
    }
    return ret;
}
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++;
                g[last].push_back(ids[a]);
                rg[ids[a]].push_back(last);
                g[last].push_back(ids[b]);
                rg[ids[b]].push_back(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(1);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        buffer.push_back({i, 1});
    }
    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]);
                buffer.push_back({ids[a], -1});
                buffer.push_back({ids[b], -1});
                last++;
                ids[a] = ids[b] = last;
                buffer.push_back({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: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5