Submission #501140

#	Time	Username	Problem	Language	Result	Execution time	Memory
501140		Joo	Regions (IOI09_regions)	C++17	30 / 100	1155 ms	59344 KiB

regions

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

const int N = 2e5+10, MR = 510;

int n, R, Q, sz[N], cnt[MR], re[N], ans[MR][MR];
vector<int> G[N], ch[N];

void dfs1(int u, int p){
    sz[u] = 1;
    for(int v : G[u]){
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p, bool keep){
    int bc = -1;
    for(int v : G[u]) if(bc == -1 or sz[v] > sz[bc]) bc = v;

    for(int v : G[u]) if(v != bc) dfs2(v, u, 0);
    if(bc != -1){
        dfs2(bc, u, 1);
        swap(ch[u], ch[bc]);
    }
    ch[u].emplace_back(u);
    cnt[re[u]]++;

    for(int v : G[u]){
        if(v == bc) continue;
        for(int vv : ch[v]){
            cnt[re[vv]]++;
            ch[u].emplace_back(vv);
        }
    }
    for(int i = 1; i <= R; i++) ans[re[u]][i] += cnt[i];

    if(keep == 0){
        for(int v : ch[u]) cnt[re[v]]--;
    }
}

int getans(int r1, int r2){
    return ans[r1][r2];
}

int main(void){
    cin >> n >> R >> Q;
    cin >> re[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> re[i];
        G[p].emplace_back(i);
    }

    dfs1(1, -1);
    dfs2(1, -1, 1);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        cout << getans(r1, r2) << endl;
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85