Submission #856383

#	Time	Username	Problem	Language	Result	Execution time	Memory
856383		hqminhuwu	Regions (IOI09_regions)	C++17	100 / 100	2620 ms	87716 KiB

regions

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
 
 
using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
 
int fst[N],lst[N],f[N],res[N][500],par[N],cnt[N],n,r,q,cur;
vector <int> a[N],w[N],ww[N];
void go (int u){
    fst[u] = ++cur;
    w[f[u]].pb(cur);
    ww[f[u]].pb(u);
    for (int v : a[u])
        go(v);
    lst[u] = cur;
}
 
int od[N];
void dfs (int u, int sum, int x){
    res[f[u]][od[x]] += sum;;
    sum += (f[u] == x);
    for (int v : a[u])
        dfs(v,sum,x);
}
 
int i,u,v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> r >> q;
    cin >> f[1];
    cnt[f[1]]++;
    forr (i,2,n)
        cin >> par[i],a[par[i]].pb(i),
        cin >> f[i],cnt[f[i]]++;
    forr (i,1,r)
        w[i].pb(0);
    go(1);
    forr (i,1,r)
        w[i].pb(oo);
    int numcmp = 0;
    forr (i,1,r){
        if (cnt[i] <= sqrt(n))
            continue;
        od[i] = ++numcmp;
        dfs(1,0,i);
    }
    while (q--){
        cin >> u >> v;
        if (od[u])
            cout <<res[v][od[u]] << endl;
        else {
            int ans = 0;
            for (int i : ww[u]){
                ans += upper_bound(all(w[v]),lst[i]) - lower_bound(all(w[v]),fst[i]);
            }
                cout << ans << endl;
        }
    }
    return 0;
}
/*
 
 
 
*/
 

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