Submission #1265839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265839		nanaseyuzuki	Regions (IOI09_regions)	C++20	100 / 100	3914 ms	40388 KiB

regions

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--  
    I love Megumi Katou ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
// #define int long long
// #define ss(a, cmp) sort(a.begin(), a.end(), cmp);
// #define ss(a) sort(a.begin(), a.end());
#define uq(a) a.erase(unique(a.begin(), a.end()), a.end());
using namespace std;

const int mn = 2e5 + 5, mod = 1e9 + 7, base = 311, B = 500;

int n, r, q, c[mn], st[mn], ft[mn], sz[mn], big[mn], not_small[mn], sub[mn], hv[mn], pp[mn], all[mn], euler[mn], nen[mn], timer = 0, cnt[2][505][25005];
vector<int> a[mn], heavy, adj[mn];

void pre_dfs(int u, int p){
    st[u] = ++ timer;
    sz[u] = 1;
    euler[timer] = u;
    for(auto v : a[u]){
        if(v == p) continue;
        pre_dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[big[u]]) big[u] = v;
    }
    ft[u] = timer;
}

void build0(int u, int p){
    if(hv[c[u]]) pp[c[u]] ++;
    for(auto i : heavy){
        cnt[0][nen[i]][c[u]] += pp[i];
        if(i == c[u]) cnt[0][nen[i]][c[u]] --;
    }
    for(auto v : a[u]){
        if(v == p) continue;
        build0(v, u);
    }
    if(hv[c[u]]) pp[c[u]] --;
}

void add(int u, int p, int delta){
    if(hv[c[u]]) sub[c[u]] += delta;
    for(auto v : a[u]){
        if(v != p && !not_small[v]){
            add(v, u, delta);
        }
    }
}

void build1(int u, int p, bool keep){
    for(auto v : a[u]){
        if(v != p && v != big[u]){
            build1(v, u, false);
        }
    }

    if(big[u]){
        build1(big[u], u, true);
        not_small[big[u]] = 1;
    }
    
    add(u, p, 1);

    if(big[u]) not_small[big[u]] = 0;
    for(auto i : heavy){
        cnt[1][nen[i]][c[u]] += sub[i];
    }
    
    if(!keep){
        for(auto i : heavy) sub[i] = 0;
    }
}

int bit[mn];

void upd(int u, int val){
    while(u <= n){
        bit[u] += val;
        u += (u & -u);
    }
}

int get(int u){
    int res = 0;
    while(u){
        res += bit[u];
        u -= (u & -u);
    }
    return res;
}

void solve(){
    cin >> n >> r >> q;
    cin >> c[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        a[p].push_back(i);
        cin >> c[i];
    }
    pre_dfs(1, 0);
    for(int i = 1; i <= n; i++) all[c[i]] ++;
    int qq = 0;
    for(int i = 1; i <= r; i++){
        if(all[i] > B){
            heavy.push_back(i);
            hv[i] = 1;
            nen[i] = qq ++;
        }
    }
    for(int i = 1; i <= n; i++) if(all[c[i]] <= B) adj[c[i]].push_back(i);
    build0(1, 0);
    build1(1, 0, 0);
    while(q--){
        int r1, r2; cin >> r1 >> r2;
        if(all[r1] > B) cout << cnt[0][nen[r1]][r2] << '\n';
        else if(all[r2] > B) cout << cnt[1][nen[r2]][r1] << '\n';
        else{
            for(auto i : adj[r2]) upd(st[i], 1);         
            int res = 0;
            for(auto i : adj[r1]){
                res += get(ft[i]) - get(st[i] - 1);
            }
            for(auto i : adj[r2]) upd(st[i], -1);
            cout << res << '\n';         
        }
        cout << flush;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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