oj.uz

Submission #53597

# Submission time Handle Problem Language Result Execution time Memory
53597 2018-06-30T09:23:44 Z 노영훈(#1418) Regions (IOI09_regions) C++11
15 / 100
 8000 ms 30108 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<pii> Q[25010];
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);
        Q[H[i]].push_back({x,-H[i]});
        Q[H[i]].push_back({sub[x],H[i]});
    }
    for(int i=1; i<=r; i++){
        sort(P[i].begin(), P[i].end());
        sort(Q[i].begin(), Q[i].end());
    }
}

int solve(int x, int y){
    vector<pii> A;
    int p1=0, p2=0, sz1=Q[x].size(), sz2=P[y].size();
    while(p1<sz1 || p2<sz2){
        if(p2==sz2){
            A.push_back(Q[x][p1]);
            p1++; continue;
        }
        if(p1==sz1){
            A.push_back({P[y][p2], y});
            p2++; continue;
        }
        int u=Q[x][p1].first, v=P[y][p2];
        if(u<v || (u==v && Q[x][p1].second<0)){
            A.push_back(Q[x][p1]);
            p1++; continue;
        }
        else{
            A.push_back({P[y][p2], y});
            p2++; continue;
        }
    }
    int cnt=0, ans=0;
    for(pii &p:A){
        int pos=p.first, idx=p.second;
        if(idx==y){
            ans+=cnt;
            continue;
        }
        if(idx<0){
            cnt++;
        }
        else{
            cnt--;
        }
    }
    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;
}

Compilation message

regions.cpp: In function 'int solve(int, int)':
regions.cpp:63:13: warning: unused variable 'pos' [-Wunused-variable]
         int pos=p.first, idx=p.second;
             ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 7 ms 6324 KB Output is correct
3 Correct 8 ms 6376 KB Output is correct
4 Correct 11 ms 6376 KB Output is correct
5 Correct 10 ms 6376 KB Output is correct
6 Correct 19 ms 6376 KB Output is correct
7 Correct 37 ms 6376 KB Output is correct
8 Correct 53 ms 6612 KB Output is correct
9 Correct 34 ms 6876 KB Output is correct
10 Correct 69 ms 7004 KB Output is correct
11 Correct 131 ms 7416 KB Output is correct
12 Correct 105 ms 8056 KB Output is correct
13 Correct 134 ms 8056 KB Output is correct
14 Correct 240 ms 8768 KB Output is correct
15 Correct 304 ms 11452 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 13380 KB Time limit exceeded
2 Execution timed out 8032 ms 13380 KB Time limit exceeded
3 Execution timed out 8016 ms 15164 KB Time limit exceeded
4 Incorrect 263 ms 15164 KB Unexpected end of file - int32 expected
5 Incorrect 376 ms 15164 KB Unexpected end of file - int32 expected
6 Incorrect 929 ms 15164 KB Unexpected end of file - int32 expected
7 Incorrect 1428 ms 15164 KB Unexpected end of file - int32 expected
8 Incorrect 1541 ms 16716 KB Unexpected end of file - int32 expected
9 Incorrect 1869 ms 18764 KB Unexpected end of file - int32 expected
10 Incorrect 3180 ms 23024 KB Unexpected end of file - int32 expected
11 Incorrect 3666 ms 23024 KB Unexpected end of file - int32 expected
12 Execution timed out 8007 ms 23024 KB Time limit exceeded
13 Execution timed out 8080 ms 23024 KB Time limit exceeded
14 Execution timed out 8034 ms 23024 KB Time limit exceeded
15 Execution timed out 8082 ms 25188 KB Time limit exceeded
16 Execution timed out 8038 ms 30108 KB Time limit exceeded
17 Execution timed out 8069 ms 30108 KB Time limit exceeded