oj.uz

답안 #53548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53548 2018-06-30T07:49:13 Z !?!?(#2015) 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){
    printf("%d\n", x);
    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);
    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:49: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:53: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:56: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:62: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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5496 KB Output is correct
2 Correct 7 ms 5684 KB Output is correct
3 Correct 9 ms 5892 KB Output is correct
4 Correct 8 ms 5892 KB Output is correct
5 Correct 12 ms 5892 KB Output is correct
6 Correct 32 ms 5976 KB Output is correct
7 Correct 19 ms 6132 KB Output is correct
8 Correct 34 ms 6132 KB Output is correct
9 Correct 68 ms 6288 KB Output is correct
10 Correct 56 ms 6336 KB Output is correct
11 Correct 116 ms 6588 KB Output is correct
12 Correct 130 ms 6972 KB Output is correct
13 Correct 168 ms 6972 KB Output is correct
14 Correct 294 ms 7244 KB Output is correct
15 Correct 366 ms 9672 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8010 ms 10044 KB Time limit exceeded
2 Execution timed out 8037 ms 10044 KB Time limit exceeded
3 Execution timed out 8032 ms 11852 KB Time limit exceeded
4 Incorrect 279 ms 11852 KB Unexpected end of file - int32 expected
5 Incorrect 425 ms 11852 KB Unexpected end of file - int32 expected
6 Incorrect 1656 ms 11852 KB Unexpected end of file - int32 expected
7 Incorrect 1741 ms 11852 KB Unexpected end of file - int32 expected
8 Incorrect 1450 ms 14028 KB Unexpected end of file - int32 expected
9 Incorrect 2634 ms 14100 KB Unexpected end of file - int32 expected
10 Incorrect 5427 ms 18764 KB Unexpected end of file - int32 expected
11 Incorrect 5852 ms 18764 KB Unexpected end of file - int32 expected
12 Incorrect 5628 ms 18764 KB Unexpected end of file - int32 expected
13 Incorrect 6457 ms 18764 KB Unexpected end of file - int32 expected
14 Execution timed out 7774 ms 18764 KB Time limit exceeded (wall clock)
15 Execution timed out 7584 ms 19404 KB Time limit exceeded (wall clock)
16 Execution timed out 7772 ms 24780 KB Time limit exceeded (wall clock)
17 Execution timed out 7810 ms 24780 KB Time limit exceeded (wall clock)