oj.uz

Submission #94578

# Submission time Handle Problem Language Result Execution time Memory
94578 2019-01-21T08:35:32 Z Retro3014 Regions (IOI09_regions) C++17
0 / 100
 913 ms 102648 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);
            }
        }
    }
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 6264 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 6264 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 6440 KB Time limit exceeded (wall clock)
7 Execution timed out 6 ms 6652 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 6904 KB Time limit exceeded (wall clock)
9 Execution timed out 11 ms 8060 KB Time limit exceeded (wall clock)
10 Execution timed out 15 ms 9720 KB Time limit exceeded (wall clock)
11 Execution timed out 20 ms 11260 KB Time limit exceeded (wall clock)
12 Execution timed out 23 ms 12920 KB Time limit exceeded (wall clock)
13 Execution timed out 30 ms 13748 KB Time limit exceeded (wall clock)
14 Execution timed out 45 ms 15352 KB Time limit exceeded (wall clock)
15 Execution timed out 38 ms 19896 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 151 ms 24716 KB Time limit exceeded (wall clock)
2 Execution timed out 129 ms 25784 KB Time limit exceeded (wall clock)
3 Execution timed out 103 ms 28628 KB Time limit exceeded (wall clock)
4 Execution timed out 41 ms 17016 KB Time limit exceeded (wall clock)
5 Execution timed out 46 ms 21624 KB Time limit exceeded (wall clock)
6 Execution timed out 251 ms 27896 KB Time limit exceeded (wall clock)
7 Execution timed out 341 ms 38916 KB Time limit exceeded (wall clock)
8 Execution timed out 460 ms 59176 KB Time limit exceeded (wall clock)
9 Execution timed out 220 ms 64120 KB Time limit exceeded (wall clock)
10 Execution timed out 913 ms 102648 KB Time limit exceeded (wall clock)
11 Execution timed out 314 ms 80920 KB Time limit exceeded (wall clock)
12 Execution timed out 494 ms 82708 KB Time limit exceeded (wall clock)
13 Execution timed out 316 ms 81044 KB Time limit exceeded (wall clock)
14 Execution timed out 854 ms 82452 KB Time limit exceeded (wall clock)
15 Execution timed out 442 ms 97076 KB Time limit exceeded (wall clock)
16 Execution timed out 371 ms 93596 KB Time limit exceeded (wall clock)
17 Execution timed out 622 ms 91988 KB Time limit exceeded (wall clock)