oj.uz

Submission #53544

# Submission time Handle Problem Language Result Execution time Memory
53544 2018-06-30T07:42:46 Z 노영훈(#1418) Regions (IOI09_regions) C++11
15 / 100
 8000 ms 24780 KB 
#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<<endl;
}
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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5496 KB Output is correct
2 Correct 7 ms 5584 KB Output is correct
3 Correct 8 ms 5764 KB Output is correct
4 Correct 7 ms 5764 KB Output is correct
5 Correct 13 ms 5872 KB Output is correct
6 Correct 22 ms 5920 KB Output is correct
7 Correct 19 ms 5920 KB Output is correct
8 Correct 31 ms 5920 KB Output is correct
9 Correct 56 ms 6304 KB Output is correct
10 Correct 52 ms 6324 KB Output is correct
11 Correct 68 ms 6580 KB Output is correct
12 Correct 123 ms 6960 KB Output is correct
13 Correct 106 ms 6960 KB Output is correct
14 Correct 241 ms 7224 KB Output is correct
15 Correct 317 ms 9660 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8061 ms 10044 KB Time limit exceeded
2 Execution timed out 8009 ms 10044 KB Time limit exceeded
3 Execution timed out 8029 ms 11836 KB Time limit exceeded
4 Incorrect 248 ms 11836 KB Unexpected end of file - int32 expected
5 Incorrect 339 ms 11836 KB Unexpected end of file - int32 expected
6 Incorrect 1435 ms 11836 KB Unexpected end of file - int32 expected
7 Incorrect 1716 ms 11836 KB Unexpected end of file - int32 expected
8 Incorrect 1346 ms 14032 KB Unexpected end of file - int32 expected
9 Incorrect 2324 ms 14032 KB Unexpected end of file - int32 expected
10 Incorrect 4851 ms 18764 KB Unexpected end of file - int32 expected
11 Incorrect 6305 ms 18764 KB Unexpected end of file - int32 expected
12 Incorrect 5256 ms 18764 KB Unexpected end of file - int32 expected
13 Incorrect 6405 ms 18764 KB Unexpected end of file - int32 expected
14 Execution timed out 7781 ms 18764 KB Time limit exceeded (wall clock)
15 Execution timed out 7605 ms 19420 KB Time limit exceeded (wall clock)
16 Execution timed out 7763 ms 24780 KB Time limit exceeded (wall clock)
17 Execution timed out 7890 ms 24780 KB Time limit exceeded (wall clock)