oj.uz

Submission #53550

# Submission time Handle Problem Language Result Execution time Memory
53550 2018-06-30T07:53:22 Z !?!?(#2015) Regions (IOI09_regions) C++11
15 / 100
 8000 ms 28876 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){
    printf("%d\n", x);
    fflush(stdout);
}
vector<int> P[MX]; // 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(){
    scanf("%d%d%d", &n, &r, &q);
    for(int i=1; i<=n; i++){
        int a,b;
        if(i==1){
            scanf("%d", &a); H[i]=a;
        }
        else{
            scanf("%d%d", &a, &b);
            G[a].push_back(i); H[i]=b;
        }
    }
    init();
    for(; q--; ){
        int r1, r2; scanf("%d%d", &r1, &r2);
        out(solve(r1,r2));
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &r, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a); H[i]=a;
             ~~~~~^~~~~~~~~~
regions.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:61:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int r1, r2; scanf("%d%d", &r1, &r2);
                     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 9 ms 9784 KB Output is correct
3 Correct 11 ms 9860 KB Output is correct
4 Correct 16 ms 9860 KB Output is correct
5 Correct 18 ms 9860 KB Output is correct
6 Correct 32 ms 10052 KB Output is correct
7 Correct 37 ms 10052 KB Output is correct
8 Correct 38 ms 10052 KB Output is correct
9 Correct 55 ms 10484 KB Output is correct
10 Correct 97 ms 10484 KB Output is correct
11 Correct 126 ms 10680 KB Output is correct
12 Correct 143 ms 11064 KB Output is correct
13 Correct 117 ms 11064 KB Output is correct
14 Correct 403 ms 11340 KB Output is correct
15 Correct 338 ms 13772 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8035 ms 14160 KB Time limit exceeded
2 Execution timed out 8063 ms 14160 KB Time limit exceeded
3 Execution timed out 8044 ms 15948 KB Time limit exceeded
4 Incorrect 295 ms 15948 KB Unexpected end of file - int32 expected
5 Incorrect 362 ms 15948 KB Unexpected end of file - int32 expected
6 Incorrect 1565 ms 15948 KB Unexpected end of file - int32 expected
7 Incorrect 1762 ms 15948 KB Unexpected end of file - int32 expected
8 Incorrect 1650 ms 18172 KB Unexpected end of file - int32 expected
9 Incorrect 2683 ms 18172 KB Unexpected end of file - int32 expected
10 Incorrect 5567 ms 22860 KB Unexpected end of file - int32 expected
11 Incorrect 6254 ms 22860 KB Unexpected end of file - int32 expected
12 Incorrect 5568 ms 22860 KB Unexpected end of file - int32 expected
13 Incorrect 5674 ms 22860 KB Unexpected end of file - int32 expected
14 Execution timed out 8041 ms 22860 KB Time limit exceeded
15 Execution timed out 8021 ms 23540 KB Time limit exceeded
16 Execution timed out 7923 ms 28876 KB Time limit exceeded (wall clock)
17 Execution timed out 8077 ms 28876 KB Time limit exceeded (wall clock)