oj.uz

Submission #94579

# Submission time Handle Problem Language Result Execution time Memory
94579 2019-01-21T08:43:48 Z Retro3014 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 102532 KB 
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>


using namespace std;
#define MAX_N 200000
#define MAX_SN 500
#define MAX_R 25000
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];
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]);
    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]]);
                }
                printf("%d\n", ans);
            }
        }
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:60: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:70: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:76: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:102:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(reg[i].size()>=(int)sqrt(N)){
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~
regions.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<bigR.size(); i++){
                  ~^~~~~~~~~~~~
regions.cpp:122:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<reg[a].size(); i++){
                              ~^~~~~~~~~~~~~~
regions.cpp:83: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:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &H[i]);
             ~~~~~^~~~~~~~~~~~~
regions.cpp:92: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:114: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 6260 KB Output is correct
2 Correct 6 ms 6136 KB Output is correct
3 Correct 9 ms 6140 KB Output is correct
4 Correct 11 ms 6264 KB Output is correct
5 Correct 10 ms 6392 KB Output is correct
6 Correct 26 ms 6392 KB Output is correct
7 Correct 36 ms 6648 KB Output is correct
8 Correct 41 ms 6776 KB Output is correct
9 Correct 37 ms 8148 KB Output is correct
10 Correct 82 ms 9844 KB Output is correct
11 Correct 200 ms 11128 KB Output is correct
12 Correct 254 ms 13048 KB Output is correct
13 Correct 283 ms 13864 KB Output is correct
14 Correct 449 ms 15288 KB Output is correct
15 Correct 571 ms 19960 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2023 ms 24828 KB Output is correct
2 Correct 2348 ms 25912 KB Output is correct
3 Correct 5760 ms 28640 KB Output is correct
4 Correct 416 ms 17016 KB Output is correct
5 Correct 587 ms 21756 KB Output is correct
6 Correct 807 ms 27920 KB Output is correct
7 Correct 1185 ms 38904 KB Output is correct
8 Correct 1522 ms 59304 KB Output is correct
9 Correct 5619 ms 64124 KB Output is correct
10 Correct 4778 ms 102532 KB Output is correct
11 Execution timed out 8058 ms 81000 KB Time limit exceeded
12 Correct 3114 ms 82892 KB Output is correct
13 Correct 4458 ms 80944 KB Output is correct
14 Correct 4605 ms 82432 KB Output is correct
15 Correct 7634 ms 97224 KB Output is correct
16 Execution timed out 8013 ms 93732 KB Time limit exceeded
17 Correct 7397 ms 92084 KB Output is correct