Submission #1326575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326575		adiyer	Regions (IOI09_regions)	C++20	0 / 100	210 ms	37072 KiB

regions

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>    
#include <ext/pb_ds/tree_policy.hpp>  

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update >

typedef long long ll;

const int N = 200003;
const int B = 650;

ll k;
ll dp[N], cnt[N / B][25002], up[N / B][25002];

int n, m, q, tick, cur, num;
int a[N], p[N], tin[N], tout[N], id[N]; 

vector < int > g[N], r[N];

ordered_set st;

void dfs(int v){
    tin[v] = ++tick; 
    for(int u : g[v]) dfs(u);
    tout[v] = ++tick;
}

void calc(int v, int tp){
    cnt[id[tp]][a[v]] += cur;
    if(a[v] == tp) cur++; 
    for(int u : g[v]) calc(u, tp), dp[v] += dp[u];
    if(a[v] == tp) cur--;
    up[id[tp]][a[v]] += dp[v] - (a[v] == tp);
}

bool cmp(int i, int j){
    return tin[i] < tin[j];
}

void solve(){
    cin >> n >> m >> q >> a[1], r[a[1]].push_back(1);
    for(int i = 2; i <= n; i++) cin >> p[i] >> a[i], g[p[i]].push_back(i), r[a[i]].push_back(i);
    dfs(1);
    for(int i = 1; i <= m; i++){
        if(r[i].size() > B){
            for(ll x : r[i]) dp[x] = 1;
            id[i] = ++num, calc(1, i);
            fill(dp, dp + n + 1, 0);
        }
        else{
            sort(r[i].begin(), r[i].end(), cmp);
        }
    }
    while(q--){
        int r1, r2, i = 0;
        cin >> r1 >> r2;
        if(r[r1].size() > B) cout << cnt[id[r1]][r2] << '\n';
        else if(r[r2].size() > B) cout << up[id[r2]][r1] << '\n';
        else{
            k = 0, st.clear();
            for(int x : r[r2]) st.insert(tout[x]);
            for(int x : r[r1]){
                while(i < r[r2].size() && tin[r[r2][i]] < tin[x]) st.erase(tout[r[r2][i]]), i++;
                k += st.order_of_key(tout[x]);
            }
            cout << k << '\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

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