Submission #53541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53541	2018-06-30T07:38:33 Z	노영훈(#1418)	Regions (IOI09_regions)	C++11	0 / 100	138 ms	24880 KB

regions

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;

void out(int x){
    cout<<x<<'\n';
    fflush(stdout);
}
vector<int> P[25010]; // dfs indexes
vector<int> G[MX];
int n, H[MX], q, r;

int num[MX], sub[MX], now;

void dfs(int v){
    num[v]=++now; int &r=sub[num[v]]; r=num[v];
    for(int x:G[v]){
        dfs(x);
        r=max(r, sub[num[x]]);
    }
}

void init(){
    dfs(1);
    for(int i=1; i<=n; i++){
        int x=num[i];
        P[H[i]].push_back(x);
    }
    for(int i=1; i<=r; i++)
        sort(P[i].begin(), P[i].end());
}

int solve(int x, int y){
    vector<int> &V=P[x], &W=P[y];

    int ans=0;
    for(int l:V){
        int r=sub[l];
        ans+=upper_bound(W.begin(), W.end(), r) - lower_bound(W.begin(), W.end(), l);
    }
    return ans;

}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>r>>q;
    for(int i=1; i<=n; i++){
        int a,b;
        if(i==1){
            cin>>a; H[i]=a;
        }
        else{
            cin>>a>>b;
            G[a].push_back(i); H[i]=b;
        }
    }
    init();
    for(; q--; ){
        int r1, r2; cin>>r1>>r2;
        out(solve(r1,r2));
    }
    return 0;
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5 ms	5496 KB	Time limit exceeded (wall clock)
2	Execution timed out	6 ms	5684 KB	Time limit exceeded (wall clock)
3	Execution timed out	6 ms	5760 KB	Time limit exceeded (wall clock)
4	Execution timed out	5 ms	5760 KB	Time limit exceeded (wall clock)
5	Execution timed out	5 ms	5760 KB	Time limit exceeded (wall clock)
6	Execution timed out	6 ms	5872 KB	Time limit exceeded (wall clock)
7	Execution timed out	7 ms	5872 KB	Time limit exceeded (wall clock)
8	Execution timed out	7 ms	5872 KB	Time limit exceeded (wall clock)
9	Execution timed out	8 ms	6256 KB	Time limit exceeded (wall clock)
10	Execution timed out	13 ms	6256 KB	Time limit exceeded (wall clock)
11	Execution timed out	11 ms	6516 KB	Time limit exceeded (wall clock)
12	Execution timed out	20 ms	6972 KB	Time limit exceeded (wall clock)
13	Execution timed out	14 ms	6972 KB	Time limit exceeded (wall clock)
14	Execution timed out	16 ms	7228 KB	Time limit exceeded (wall clock)
15	Execution timed out	20 ms	9700 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	36 ms	10044 KB	Time limit exceeded (wall clock)
2	Execution timed out	35 ms	10044 KB	Time limit exceeded (wall clock)
3	Execution timed out	37 ms	11836 KB	Time limit exceeded (wall clock)
4	Execution timed out	29 ms	11836 KB	Time limit exceeded (wall clock)
5	Execution timed out	18 ms	11836 KB	Time limit exceeded (wall clock)
6	Execution timed out	25 ms	11836 KB	Time limit exceeded (wall clock)
7	Execution timed out	36 ms	11836 KB	Time limit exceeded (wall clock)
8	Execution timed out	42 ms	14028 KB	Time limit exceeded (wall clock)
9	Execution timed out	68 ms	14028 KB	Time limit exceeded (wall clock)
10	Execution timed out	70 ms	18764 KB	Time limit exceeded (wall clock)
11	Execution timed out	98 ms	18764 KB	Time limit exceeded (wall clock)
12	Execution timed out	138 ms	18764 KB	Time limit exceeded (wall clock)
13	Execution timed out	100 ms	18764 KB	Time limit exceeded (wall clock)
14	Execution timed out	106 ms	18764 KB	Time limit exceeded (wall clock)
15	Execution timed out	125 ms	19424 KB	Time limit exceeded (wall clock)
16	Execution timed out	100 ms	24880 KB	Time limit exceeded (wall clock)
17	Execution timed out	87 ms	24880 KB	Time limit exceeded (wall clock)