oj.uz

Submission #53641

# Submission time Handle Problem Language Result Execution time Memory
53641 2018-06-30T15:29:08 Z Diuven Regions (IOI09_regions) C++11
70 / 100
 8000 ms 33568 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; 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], 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());
    }
}

map<pii, int> D;

struct ord {
    int x, type; // 1(st), 2(pt), 3(ed)
    bool operator < (const ord &o) const {
        if(x==o.x) return type<o.type;
        return x<o.x;
    }
};

int solve(int x, int y){
    if(D.find({x,y})!=D.end()) return D[{x,y}];
    int &ans=D[pii(x,y)]; ans=0;

    vector<ord> A;
    int p1=0, p2=0, sz1=Q[x].size(), sz2=P[y].size();
    while(p1<sz1 && p2<sz2){
        ord a={Q[x][p1].first, Q[x][p1].second?3:1};
        ord b={P[y][p2], 2};
        if(a<b) A.push_back(a), p1++;
        else A.push_back(b), p2++;
    }
    while(p1<sz1){
        ord a={Q[x][p1].first, Q[x][p1].second?3:1};
        A.push_back(a); p1++;
    }
    while(p2<sz2){
        ord b={P[y][p2], 2};
        A.push_back(b); p2++;
    }
    int cnt=0;
    for(ord &o:A){
        if(o.type==1){
            cnt++;
        }
        else if(o.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();
    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 6264 KB Output is correct
2 Correct 7 ms 6264 KB Output is correct
3 Correct 8 ms 6440 KB Output is correct
4 Correct 11 ms 6440 KB Output is correct
5 Correct 14 ms 6444 KB Output is correct
6 Correct 31 ms 6520 KB Output is correct
7 Correct 35 ms 6644 KB Output is correct
8 Correct 40 ms 6740 KB Output is correct
9 Correct 78 ms 7304 KB Output is correct
10 Correct 97 ms 7548 KB Output is correct
11 Correct 151 ms 8004 KB Output is correct
12 Correct 177 ms 8824 KB Output is correct
13 Correct 180 ms 8824 KB Output is correct
14 Correct 258 ms 9356 KB Output is correct
15 Correct 260 ms 12236 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 14100 KB Output is correct
2 Correct 1646 ms 14100 KB Output is correct
3 Correct 2696 ms 18176 KB Output is correct
4 Correct 336 ms 18176 KB Output is correct
5 Correct 525 ms 18176 KB Output is correct
6 Correct 783 ms 18176 KB Output is correct
7 Correct 953 ms 18176 KB Output is correct
8 Correct 1609 ms 20872 KB Output is correct
9 Correct 2894 ms 26832 KB Output is correct
10 Correct 4603 ms 32924 KB Output is correct
11 Correct 4451 ms 32924 KB Output is correct
12 Execution timed out 8079 ms 32924 KB Time limit exceeded
13 Execution timed out 8087 ms 32924 KB Time limit exceeded
14 Execution timed out 8004 ms 32924 KB Time limit exceeded
15 Execution timed out 8022 ms 32924 KB Time limit exceeded
16 Execution timed out 8042 ms 32924 KB Time limit exceeded
17 Execution timed out 8063 ms 33568 KB Time limit exceeded