Submission #1316986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316986		aaaaaaaa	Regions (IOI09_regions)	C++20	30 / 100	555 ms	196608 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
const int mxR = 501;
vector<int> adj[mxN];
int ans[mxR][mxR], freq[mxN], r[mxN];
void dfs(int u = 1){
    freq[r[u]] += 1;
    vector<int> x(mxR + 10, 0);
    for(int j = 0; j < mxR; ++j) x[j] = freq[j];
    for(auto it : adj[u]) dfs(it);
    for(int j = 0; j < mxR; ++j) ans[r[u]][j] += freq[j] - x[j];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, k, q;
    cin >> n >> k >> q >> r[1];
    for(int i = 2, p; i <= n; ++i){
        cin >> p >> r[i];
        adj[p].push_back(i);
    }
    dfs();
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        cout << ans[r1][r2] << endl;
    }
    return 0;
}

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