Submission #1101642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101642		InvMOD	Regions (IOI09_regions)	C++14	100 / 100	3409 ms	30848 KiB

regions

#include<bits/stdc++.h>

#define pb push_back
#define all(v) (v).begin(), (v).end()

using namespace std;

const int N = 2e5+5;
const int R = 25005;
const int SZ = 500;

int n, r, q, timerDFS;
int reg[N], cnt[N], tin[N], tout[N];
vector<int> adj[N], home[R], inReg[R], regional[R];


void dfs(int x){
    tin[x] = ++timerDFS;
    home[reg[x]].pb(tin[x]);
    for(int v : adj[x]){
        dfs(v);
    }
    tout[x] = ++timerDFS;
    cnt[reg[x]] = cnt[reg[x]] + 1;
    inReg[reg[x]].pb(x);
    return;
}

void get_answer(int x, int id, int cntAsc){
    regional[id][reg[x]] += cntAsc;
    for(int v : adj[x]){
        get_answer(v, id, cntAsc + (reg[x] == id));
    }
    return;
}

int get_child(int x, int cur_reg){
    int l = tin[x], r = tout[x];
    int ub = upper_bound(all(home[cur_reg]), r) - home[cur_reg].begin();
    int lb = lower_bound(all(home[cur_reg]), l) - home[cur_reg].begin();
    return ub - lb;
}

void solve()
{
    cin >> n >> r >> q;

    cin >> reg[1];
    for(int i = 2; i <= n; i++){
        int u; cin >> u >> reg[i];
        adj[u].pb(i);
    }

    dfs(1);

    for(int i = 1; i <= r; i++){
        if(cnt[i] > SZ){
            regional[i].resize(r+1, 0);
            get_answer(1, i, 0);
        }
        sort(all(home[i]));
    }

    while(q--){
        int reg1, reg2;
        cin >> reg1 >> reg2;

        if(cnt[reg1] > SZ){
            cout << regional[reg1][reg2] <<"\n";
            cout.flush();
        }
        else{
            int answer = 0;
            for(int v : inReg[reg1]){
                answer = answer + get_child(v, reg2);
            }
            cout << answer <<"\n";
            cout.flush();
        }
    }
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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