oj.uz

Submission #1101642

# Submission time Handle Problem Language Result Execution time Memory
1101642 2024-10-16T13:12:09 Z InvMOD Regions (IOI09_regions) C++14
100 / 100
 3409 ms 30848 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 4 ms 8952 KB Output is correct
4 Correct 6 ms 8784 KB Output is correct
5 Correct 7 ms 8784 KB Output is correct
6 Correct 15 ms 8784 KB Output is correct
7 Correct 21 ms 8784 KB Output is correct
8 Correct 24 ms 8784 KB Output is correct
9 Correct 40 ms 9296 KB Output is correct
10 Correct 73 ms 9296 KB Output is correct
11 Correct 93 ms 9552 KB Output is correct
12 Correct 119 ms 9808 KB Output is correct
13 Correct 136 ms 9552 KB Output is correct
14 Correct 198 ms 10064 KB Output is correct
15 Correct 227 ms 12624 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 13144 KB Output is correct
2 Correct 1746 ms 11776 KB Output is correct
3 Correct 2389 ms 15152 KB Output is correct
4 Correct 228 ms 10320 KB Output is correct
5 Correct 317 ms 11600 KB Output is correct
6 Correct 1074 ms 11344 KB Output is correct
7 Correct 1369 ms 12112 KB Output is correct
8 Correct 1139 ms 16976 KB Output is correct
9 Correct 1878 ms 17164 KB Output is correct
10 Correct 3409 ms 21832 KB Output is correct
11 Correct 2931 ms 16668 KB Output is correct
12 Correct 1086 ms 18240 KB Output is correct
13 Correct 1572 ms 18664 KB Output is correct
14 Correct 1890 ms 19816 KB Output is correct
15 Correct 2593 ms 23636 KB Output is correct
16 Correct 2710 ms 30848 KB Output is correct
17 Correct 2601 ms 30844 KB Output is correct