oj.uz

Submission #94576

# Submission time Handle Problem Language Result Execution time Memory
94576 2019-01-21T07:52:40 Z Retro3014 Regions (IOI09_regions) C++17
0 / 100
 1262 ms 122104 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];
ll 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){
    if(seg[x][idx].s==seg[x][idx].e)    return;
    seg[x][idx].cnt++;
    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;
ll 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--;
}

ll dfs3(int x){
    ll 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("%lld\n", count1[big[a]][b]);
        }else{
            if(big[b]!=0){
                printf("%lld\n", count2[big[b]][a]);
            }else{
                ll ans = 0;
                for(int i=0; i<reg[a].size(); i++){
                    ans+=(ll)sum(b, 0, in[reg[a][i]], out[reg[a][i]]);
                }
                printf("%lld\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 'll 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 6180 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
3 Execution timed out 5 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 6312 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 6520 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 6648 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 6904 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 8056 KB Time limit exceeded (wall clock)
10 Execution timed out 14 ms 9848 KB Time limit exceeded (wall clock)
11 Execution timed out 18 ms 11128 KB Time limit exceeded (wall clock)
12 Execution timed out 25 ms 12920 KB Time limit exceeded (wall clock)
13 Execution timed out 26 ms 13816 KB Time limit exceeded (wall clock)
14 Execution timed out 47 ms 15352 KB Time limit exceeded (wall clock)
15 Execution timed out 37 ms 19832 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 175 ms 24764 KB Time limit exceeded (wall clock)
2 Execution timed out 143 ms 26128 KB Time limit exceeded (wall clock)
3 Execution timed out 114 ms 28640 KB Time limit exceeded (wall clock)
4 Execution timed out 37 ms 17016 KB Time limit exceeded (wall clock)
5 Execution timed out 45 ms 21752 KB Time limit exceeded (wall clock)
6 Execution timed out 293 ms 31224 KB Time limit exceeded (wall clock)
7 Execution timed out 336 ms 42928 KB Time limit exceeded (wall clock)
8 Execution timed out 445 ms 67108 KB Time limit exceeded (wall clock)
9 Execution timed out 236 ms 64284 KB Time limit exceeded (wall clock)
10 Execution timed out 1111 ms 122104 KB Time limit exceeded (wall clock)
11 Execution timed out 283 ms 80980 KB Time limit exceeded (wall clock)
12 Execution timed out 519 ms 83016 KB Time limit exceeded (wall clock)
13 Execution timed out 334 ms 81212 KB Time limit exceeded (wall clock)
14 Execution timed out 1262 ms 85832 KB Time limit exceeded (wall clock)
15 Execution timed out 368 ms 97396 KB Time limit exceeded (wall clock)
16 Execution timed out 409 ms 93964 KB Time limit exceeded (wall clock)
17 Execution timed out 533 ms 95636 KB Time limit exceeded (wall clock)