oj.uz

Submission #53652

# Submission time Handle Problem Language Result Execution time Memory
53652 2018-06-30T15:45:11 Z Diuven Regions (IOI09_regions) C++11
0 / 100
 114 ms 23884 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
const int MX=200010, inf=2e9;

void out(int x){
    cout<<x<<endl;
}
vector<int> P[25010]; // dfs indexes
vector<pib> 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;
    sub[num[v]]=num[v];
    for(int x:G[v]){
        dfs(x);
        sub[num[v]]=max(sub[num[v]], sub[num[x]]);
    }
}

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

unordered_map<ll, int> D;
vector<int> A; // 1(st), 2(pt), 3(ed)

int solve(int x, int y){
    return 0;
    /*
    ll idx=((ll)x<<30)+y;
    if(D.find(idx)!=D.end()) return D[idx];
    int &ans=D[idx]; ans=0;
    */
   int ans=0;

    A.clear();
    int p1=0, p2=0, sz1=Q[x].size(), sz2=P[y].size();
    while(p1<sz1 && p2<sz2){
        pii a={Q[x][p1].first, Q[x][p1].second?3:1};
        pii b={P[y][p2], 2};
        if(a<b) A.push_back(a.second), p1++;
        else A.push_back(b.second), p2++;
    }
    while(p1<sz1){
        int type=Q[x][p1].second?3:1;
        A.push_back(type); p1++;
    }
    while(p2<sz2){
        A.push_back(2); p2++;
    }
    int cnt=0;
    for(int type:A){
        if(type==1){
            cnt++;
        }
        else if(type==2){
            ans+=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();
    return 0;
    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 Incorrect 7 ms 6072 KB Unexpected end of file - int32 expected
2 Incorrect 8 ms 6324 KB Unexpected end of file - int32 expected
3 Incorrect 7 ms 6408 KB Unexpected end of file - int32 expected
4 Incorrect 9 ms 6408 KB Unexpected end of file - int32 expected
5 Incorrect 6 ms 6408 KB Unexpected end of file - int32 expected
6 Incorrect 7 ms 6408 KB Unexpected end of file - int32 expected
7 Incorrect 7 ms 6424 KB Unexpected end of file - int32 expected
8 Incorrect 7 ms 6552 KB Unexpected end of file - int32 expected
9 Incorrect 9 ms 6816 KB Unexpected end of file - int32 expected
10 Incorrect 11 ms 6816 KB Unexpected end of file - int32 expected
11 Incorrect 12 ms 7092 KB Unexpected end of file - int32 expected
12 Incorrect 14 ms 7476 KB Unexpected end of file - int32 expected
13 Incorrect 15 ms 7476 KB Unexpected end of file - int32 expected
14 Incorrect 19 ms 7612 KB Unexpected end of file - int32 expected
15 Incorrect 23 ms 10044 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 10172 KB Unexpected end of file - int32 expected
2 Incorrect 37 ms 10172 KB Unexpected end of file - int32 expected
3 Incorrect 37 ms 11980 KB Unexpected end of file - int32 expected
4 Incorrect 30 ms 11980 KB Unexpected end of file - int32 expected
5 Incorrect 25 ms 11980 KB Unexpected end of file - int32 expected
6 Incorrect 32 ms 11980 KB Unexpected end of file - int32 expected
7 Incorrect 54 ms 11980 KB Unexpected end of file - int32 expected
8 Incorrect 47 ms 13836 KB Unexpected end of file - int32 expected
9 Incorrect 81 ms 13836 KB Unexpected end of file - int32 expected
10 Incorrect 74 ms 17868 KB Unexpected end of file - int32 expected
11 Incorrect 91 ms 17868 KB Unexpected end of file - int32 expected
12 Incorrect 107 ms 17868 KB Unexpected end of file - int32 expected
13 Incorrect 83 ms 17868 KB Unexpected end of file - int32 expected
14 Incorrect 114 ms 17868 KB Unexpected end of file - int32 expected
15 Incorrect 87 ms 18204 KB Unexpected end of file - int32 expected
16 Incorrect 94 ms 23884 KB Unexpected end of file - int32 expected
17 Incorrect 86 ms 23884 KB Unexpected end of file - int32 expected