Submission #929032

#	Time	Username	Problem	Language	Result	Execution time	Memory
929032		dosts	Regions (IOI09_regions)	C++17	100 / 100	3976 ms	127676 KiB

regions

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int N = 2e5+1,MOD = 998244353,B = 125,inf  = 2e9,R = 25001;

vi c(N),edges[N],tin(N),tout(N);
vi occtin[R],ind(R);
int prec[B][N];
int timer = 1;

vi cc(B+1,0);
void dfs(int node,int p) {
    tin[node] = timer++;
    occtin[c[node]].push_back(tin[node]);
    for (auto it : edges[node]) if (it != p) dfs(it,node);
    tout[node] = timer-1;
}

void dfs2(int node,int p) {
    if (ind[c[node]] < B) cc[ind[c[node]]]++;
    for (int i=1;i<B;i++) prec[i][c[node]]+=cc[i];
    for (auto it : edges[node]) if (it != p) dfs2(it,node);
    if (ind[c[node]] < B) cc[ind[c[node]]]--;
} 



void solve() {
    int n,r,q;
    cin >> n >> r >> q;
    cin >> c[1];
    vi occ(r+1,0);
    vi posses[r+1];
    occ[c[1]] = 1;
    posses[c[1]].push_back(1);
    for (int i=2;i<=n;i++) {
        int p;
        cin >> p >> c[i];
        edges[p].push_back(i);
        occ[c[i]]++;
        posses[c[i]].push_back(i);
    } 
    dfs(1,1);
    for (int i=1;i<=r;i++) sort(all(occtin[i])); 
    vi cols(r+1);
    for (int i=1;i<=r;i++) cols[i] = i;
    sort(cols.begin()+1,cols.end(),[&](int x,int y){
        return occ[x] > occ[y];
    });
    for (int i=1;i<=r;i++) ind[cols[i]] = i;
    dfs2(1,1);
    while (q--) {
        int r1,r2;
        cin >> r1 >> r2;
        if (ind[r1] >= B) {
            int sm = 0;
            for (auto it : posses[r1]) {
                int l=  tin[it];
                int r = tout[it];
                auto it1 = upper_bound(all(occtin[r2]),r);
                auto it2 = upper_bound(all(occtin[r2]),l-1);
                sm+=it1-it2;
            } 
            cout << sm << endl;
        }
        else {
            cout << prec[ind[r1]][r2] << endl;
        }
        fflush(stdout);
    }
}           
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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