Submission #1210405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210405		spampots	Regions (IOI09_regions)	C++17	85 / 100	8019 ms	28468 KiB

regions

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


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, R, Q;
    cin >> N >> R >> Q;

    vector<vector<int>> adj(N+1);
    vector<int> region(N+1);
    vector<vector<int>> comp(R+1);

    cin >> region[1];
    for(int i = 2; i <= N; ++i){
        int x;  cin >> x;
        adj[x].push_back(i);
        cin >> region[i];
    }
    
    int timer(0);
    vector<int> in(N+1), out(N+1), euler(N+1);
    function<void(int)> dfs = [&](int node){
        in[node] = timer++;
        euler[in[node]] = node;
        comp[region[node]].push_back(in[node]);
        for(int x : adj[node])
            dfs(x);
        out[node] = timer;
    };
    dfs(1);

    for(int i = 0; i < Q; ++i){
        int r1, r2; cin >> r1 >> r2;
        int ans(0);
        for(int x : comp[r1])
            ans += lower_bound(comp[r2].begin(), comp[r2].end(), out[euler[x]]) - lower_bound(comp[r2].begin(), comp[r2].end(), x);
        cout << ans << endl;
        fflush(stdout);
    }
}

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