Submission #1210281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210281		spampots	Regions (IOI09_regions)	C++20	30 / 100	486 ms	196608 KiB

regions

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


int main(){
    // this soluion might pass for R <= 500
    int N, R, Q;
    cin >> N >> R >> Q;

    vector<vector<int>> dp(N+1, vector<int>(R+1, 0));
    vector<int> region(N+1);
    vector<vector<int>> adj(N+1);
    vector<vector<int>> ans(R+1, vector<int>(R+1, 0));

    cin >> region[1];
    for(int i = 2; i <= N; ++i){
        int x;  cin >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
        cin >> region[i];
    }

    function<void(int, int)> dfs = [&](int parent, int node){
        for(int x : adj[node]){
            if(x == parent)  continue;
            dfs(node, x);
            dp[node][region[x]] += 1;
            for(int i = 1; i <= R; ++i)
                dp[node][i] += dp[x][i];
            
        }
        for(int i = 1; i <= R; ++i){
            if(i == region[node])   continue;
            ans[region[node]][i] += dp[node][i];
        }
    };
    dfs(-1, 1);
    // for(int i = 1; i <= N; ++i){
    //     for(int j = 0; j <= R; ++j)
    //         cout << dp[i][j] << ' ';
    //     cout << endl;
    // }
    for(int i = 0; i < Q; ++i){
        int r1, r2; cin >> r1 >> r2;
        cout << ans[r1][r2] << endl;
        fflush(stdout);
    }
}

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