제출 #1258957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258957		nguyenkhangninh99	Regions (IOI09_regions)	C++20	100 / 100	3020 ms	52152 KiB

regions

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

#define int long long
const int maxn = 2e5 + 5;

int tin[maxn], out[maxn], timeDfs;
vector<int> g[maxn], p[maxn], c[maxn];
vector<vector<int>> cost;
int r[maxn], id[maxn];

void dfs(int u, int par){
    tin[u] = ++timeDfs;
    for(int v: g[u]) dfs(v, u);
    out[u] = timeDfs;
}

void dfsc(int col, int u, int cnt){
    if(r[u] == col) cnt++;
    else cost[id[col]][r[u]] += cnt;
    for(int v: g[u]) dfsc(col, v, cnt);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, rmax, q; cin >> n >> rmax >> q;

    for(int i = 1; i <= n; i++){
        if(i >= 2){
            int x; cin >> x;
            g[x].push_back(i);  
        }
        cin >> r[i];
    }

    dfs(1, -1);

    for(int i = 1; i <= n; i++){
        p[r[i]].push_back(tin[i]);
        c[r[i]].push_back(i);
    }

    int cur = -1, BLOCK = sqrt(n);
    for(int i = 1; i <= rmax; i++){
        if(p[i].size() >= BLOCK){
            id[i] = ++cur;
            cost.push_back(vector<int>(rmax+1));
            dfsc(i, 1, 0);
        }
        sort(p[i].begin(), p[i].end());
    }

    for(int i = 1; i <= q; i++){
        int r1, r2; cin >> r1 >> r2;
        if(p[r1].size() >= BLOCK) cout << cost[id[r1]][r2] << endl;
        else{
            int ans = 0;
            for(int u: c[r1]){
                int l = lower_bound(p[r2].begin(), p[r2].end(), tin[u]) - p[r2].begin();
                int r = upper_bound(p[r2].begin(), p[r2].end(), out[u]) - p[r2].begin() - 1;
                ans += r - l + 1;
            }
            cout << ans << endl;
        }
    }
}

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