제출 #94580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94580		Retro3014	Regions (IOI09_regions)	C++17	100 / 100	5924 ms	104184 KiB

regions

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 85 / 85