Submission #899731

#	Time	Username	Problem	Language	Result	Execution time	Memory
899731		boyliguanhan	Regions (IOI09_regions)	C++17	0 / 100	62 ms	14908 KiB

regions

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define N 200100
#define M 25010
using namespace __gnu_pbds;
#pragma GCC optimize(2)
#define l int
int read(){
    char x = getchar();
    int val = 0;
    while(x<'0'||x>'9')x=getchar();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar();
    return val;
}
void print(int num){
    if(num<0){
        putchar('-');
        num*=-1;
    }
    if(num>9) {
        print(num/10);
    }
    putchar((num%10)^48);
}
using namespace std;
vector<l> adj[M], peop[M];
vector<pair<l,l>> arr[M];
l region[M], t, in[M], out[M], li[M], sz[M], lg[450], ans1[450][M], ans2[M][450];
void dfs(l n){
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n])
        dfs(i);
    out[n]=t++;
    arr[region[n]].push_back({out[n],0});
}
int query(int a, int b) {
    int i = 0, j = 0, res = 0;
    int an = arr[a].size(), bn = sz[b];
    while (i < an && j < bn)
        if (arr[a][i].first < in[peop[b][j]])
            i++;
        else
            res += arr[a][i].second,j++;
    return res;
}
int main(){
    l n=read(), r=read(), q=read(), lr=0;
    region[1]=read();
    sz[region[1]]++;
    peop[region[1]].push_back(1);
    for(l i = 2; i <= n; i++){
        adj[read()].push_back(i);
        region[i] = read();
        sz[region[i]]++;
        peop[region[i]].push_back(i);
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>449) {
            li[i]=++lr;
            for(int j = 1; j <= r; j++)
                ans1[i][j]=query(i,j),ans2[j][i]=query(j,i);
        }
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        if(li[r1])
            print(ans1[li[r1]][r2]);
        else if(li[r2])
            print(ans2[r1][li[r2]]);
        else
            print(query(r1, r2));
        puts("");
        fflush(stdout);
    }
    return 0;
}

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