제출 #1326357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326357		adiyer	Regions (IOI09_regions)	C++20	3 / 100	8066 ms	50292 KiB

regions

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 3;
const int B = 1;

ll k;

int n, m, q, tick;
int a[N], p[N], tin[N], tout[N], pos[N], cnt[N][20], down[N][20];

vector < int > b[502], g[N];

void dfs(int v){
    tin[v] = ++tick, pos[tick] = v;
    for(int u : g[v]) dfs(u);
    tout[v] = tick;
}

void dfs2(int v, int tp){
    if((tin[v] + B - 1) / B != tp) down[tp][a[v]]++;
    for(int u : g[v]) dfs2(u, tp);
}

void solve(){
    cin >> n >> m >> q >> a[1];
    for(int i = 2; i <= n; i++) cin >> p[i] >> a[i], g[p[i]].push_back(i);
    dfs(1);
    for(int i = 1; i <= n; i++) b[(i + B - 1) / B].push_back(pos[i]), cnt[(i + B - 1) / B][a[pos[i]]]++;
    for(int i = 1; i <= (n + B - 1) / B; i++) dfs2(pos[(i - 1) * B + 1], i);
    while(q--){
        int r1, r2;
        cin >> r1 >> r2, k = 0;
        for(int i = 1; i <= (n + B - 1) / B; i++) k += cnt[i][r1] * 1ll * down[i][r2];
        cout << k << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

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