oj.uz

Submission #53656

# Submission time Handle Problem Language Result Execution time Memory
53656 2018-06-30T15:54:18 Z Diuven Regions (IOI09_regions) C++11
100 / 100
 6917 ms 44460 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<<'\n'<<flush;
}
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);
    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;
unordered_map<ll, bool> done;
// 1(st), 2(pt), 3(ed)

int solve(int x, int y){
    ll idx=((ll)x<<30)+y;
    if(done[idx]) return D[idx];
    int &ans=D[idx]; ans=0; done[idx]=true;
    int cnt=0;

    int p1=0, p2=0, sz1=Q[x].size(), sz2=P[y].size();
    while(p1<sz1 && p2<sz2){
        int x1=Q[x][p1].first, x2=P[y][p2];
        int t1=Q[x][p1].second?3:1, t2=2;
        if(x1<x2 || (x1==x2 && t1<t2)){
            if(t1==1) cnt++;
            else cnt--;
            p1++;
        }
        else ans+=cnt, p2++;
    }
    while(p1<sz1){
        if(Q[x][p1].second) cnt--;
        else cnt++;
        p1++;
    }
    while(p2<sz2){
        ans+=cnt; p2++;
    }
    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 6136 KB Output is correct
2 Correct 8 ms 6236 KB Output is correct
3 Correct 9 ms 6248 KB Output is correct
4 Correct 11 ms 6248 KB Output is correct
5 Correct 13 ms 6308 KB Output is correct
6 Correct 15 ms 6516 KB Output is correct
7 Correct 25 ms 6704 KB Output is correct
8 Correct 34 ms 6932 KB Output is correct
9 Correct 59 ms 7376 KB Output is correct
10 Correct 91 ms 7712 KB Output is correct
11 Correct 151 ms 8176 KB Output is correct
12 Correct 207 ms 8992 KB Output is correct
13 Correct 172 ms 9236 KB Output is correct
14 Correct 172 ms 9532 KB Output is correct
15 Correct 270 ms 12692 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 14760 KB Output is correct
2 Correct 1139 ms 14760 KB Output is correct
3 Correct 1677 ms 19960 KB Output is correct
4 Correct 291 ms 19960 KB Output is correct
5 Correct 310 ms 19960 KB Output is correct
6 Correct 533 ms 19960 KB Output is correct
7 Correct 873 ms 19960 KB Output is correct
8 Correct 1312 ms 22552 KB Output is correct
9 Correct 1919 ms 30172 KB Output is correct
10 Correct 2905 ms 36312 KB Output is correct
11 Correct 2839 ms 36312 KB Output is correct
12 Correct 3479 ms 36312 KB Output is correct
13 Correct 5151 ms 36312 KB Output is correct
14 Correct 6917 ms 36312 KB Output is correct
15 Correct 5141 ms 38828 KB Output is correct
16 Correct 5367 ms 44460 KB Output is correct
17 Correct 4344 ms 44460 KB Output is correct