oj.uz

Submission #94580

# Submission time Handle Problem Language Result Execution time Memory
94580 2019-01-21T08:58:49 Z Retro3014 Regions (IOI09_regions) C++17
100 / 100
 5924 ms 104184 KB 
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>


using namespace std;
#define MAX_N 200000
#define MAX_SN 500
#define MAX_R 25001
typedef long long ll;


int N, R, Q, H[MAX_N+1], P[MAX_N+1];
vector<int> graph[MAX_N+1], reg[MAX_R], reg2[MAX_R];
int big[MAX_R+1], cnt=0;    vector<int> bigR;
int in[MAX_N+1], out[MAX_N+1];
int count1[MAX_SN+1][MAX_R+1], count2[MAX_SN+1][MAX_R+1];


struct SEG{
    int s, e;
    int l=-1, r=-1;
    int cnt = 0;
};
vector<SEG> seg[MAX_R+1];

void update(int x, int idx, int y){
    seg[x][idx].cnt++;
    if(seg[x][idx].s==seg[x][idx].e)    return;
    if((seg[x][idx].s+seg[x][idx].e)/2>=y){
        if(seg[x][idx].l==-1){
            seg[x][idx].l = (int)seg[x].size();
            seg[x].push_back({seg[x][idx].s, (seg[x][idx].s+seg[x][idx].e)/2, -1, -1, 0});
        }
        update(x, seg[x][idx].l, y);
    }else{
        if(seg[x][idx].r==-1){
            seg[x][idx].r = (int)seg[x].size();
            seg[x].push_back({(seg[x][idx].s+seg[x][idx].e)/2+1, seg[x][idx].e, -1, -1, 0});
        }
        update(x, seg[x][idx].r, y);
    }
}

int sum(int x, int idx, int y, int z){
    if(idx==-1) return 0;
    if(seg[x][idx].s>z || seg[x][idx].e<y)  return 0;
    if(y<=seg[x][idx].s && seg[x][idx].e<=z)    return seg[x][idx].cnt;
    return sum(x, seg[x][idx].l, y, z)+sum(x, seg[x][idx].r, y, z);
}

void dfs(int x){
    in[x]=++cnt;
    update(H[x], 0, in[x]);
    reg2[H[x]].push_back(in[x]);
    for(int i=0; i<graph[x].size(); i++)    dfs(graph[x][i]);
    out[x]=cnt;
}

int t;
int c = 0;

void dfs2(int x){
    if(H[x]==bigR[t])   c++;
    else   count1[t][H[x]]+=c;
    for(int i=0; i<graph[x].size(); i++)    dfs2(graph[x][i]);
    if(H[x]==bigR[t])   c--;
}

int dfs3(int x){
    int k = 0;
    for(int i=0; i<graph[x].size(); i++)    k+=dfs3(graph[x][i]);
    if(H[x]==bigR[t])   k++;
    else    count2[t][H[x]]+=k;
    return k;
}

int main(){
    scanf("%d%d%d", &N, &R, &Q);
    for(int i=1; i<=R; i++){
        seg[i].push_back({1, N, -1, -1, 0});
    }
    for(int i=1; i<=N; i++){
        if(i==1){
            scanf("%d", &H[i]);
            P[i] = -1;
        }else{
            scanf("%d%d", &P[i], &H[i]);
            graph[P[i]].push_back(i);
            //graph[i].push_back(P[i]);
        }
        reg[H[i]].push_back(i);
    }
    dfs(1);
    cnt=0;
    bigR.push_back(0);
    for(int i=1; i<=R; i++){
        if(reg[i].size()>=(int)sqrt(N)){
            big[i]=++cnt;
            bigR.push_back(i);
        }
    }
    for(int i=1; i<bigR.size(); i++){
        t = i;
        dfs2(1);
        dfs3(1);
    }
    for(int i=0; i<Q; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        if(big[a]!=0){
            printf("%d\n", count1[big[a]][b]);
        }else{
            if(big[b]!=0){
                printf("%d\n", count2[big[b]][a]);
            }else{
                int ans = 0;
                for(int i=0; i<reg[a].size(); i++){
                    //ans+=sum(b, 0, in[reg[a][i]], out[reg[a][i]]);
                    ans+=upper_bound(reg2[b].begin(), reg2[b].end(), out[reg[a][i]])-lower_bound(reg2[b].begin(), reg2[b].end(), in[reg[a][i]]);
                }
                printf("%d\n", ans);
            }
        }
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++)    dfs(graph[x][i]);
                  ~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int)':
regions.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++)    dfs2(graph[x][i]);
                  ~^~~~~~~~~~~~~~~~
regions.cpp: In function 'int dfs3(int)':
regions.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++)    k+=dfs3(graph[x][i]);
                  ~^~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:99:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(reg[i].size()>=(int)sqrt(N)){
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~
regions.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<bigR.size(); i++){
                  ~^~~~~~~~~~~~
regions.cpp:119:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<reg[a].size(); i++){
                              ~^~~~~~~~~~~~~~
regions.cpp:80: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:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &H[i]);
             ~~~~~^~~~~~~~~~~~~
regions.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &P[i], &H[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6904 KB Output is correct
2 Correct 6 ms 6776 KB Output is correct
3 Correct 10 ms 6948 KB Output is correct
4 Correct 13 ms 6776 KB Output is correct
5 Correct 14 ms 7036 KB Output is correct
6 Correct 27 ms 7160 KB Output is correct
7 Correct 33 ms 7160 KB Output is correct
8 Correct 39 ms 7416 KB Output is correct
9 Correct 56 ms 8676 KB Output is correct
10 Correct 92 ms 10488 KB Output is correct
11 Correct 147 ms 11896 KB Output is correct
12 Correct 168 ms 13688 KB Output is correct
13 Correct 230 ms 14968 KB Output is correct
14 Correct 373 ms 16376 KB Output is correct
15 Correct 382 ms 20876 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 25912 KB Output is correct
2 Correct 1773 ms 27372 KB Output is correct
3 Correct 2785 ms 29560 KB Output is correct
4 Correct 337 ms 17784 KB Output is correct
5 Correct 355 ms 22364 KB Output is correct
6 Correct 674 ms 28792 KB Output is correct
7 Correct 942 ms 40108 KB Output is correct
8 Correct 1253 ms 60440 KB Output is correct
9 Correct 2859 ms 65064 KB Output is correct
10 Correct 3359 ms 104184 KB Output is correct
11 Correct 5924 ms 82696 KB Output is correct
12 Correct 1916 ms 83476 KB Output is correct
13 Correct 2644 ms 82292 KB Output is correct
14 Correct 3754 ms 83352 KB Output is correct
15 Correct 3750 ms 98840 KB Output is correct
16 Correct 3708 ms 95360 KB Output is correct
17 Correct 3523 ms 92712 KB Output is correct