제출 #427418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427418		pliam	Regions (IOI09_regions)	C++14	100 / 100	5978 ms	33596 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define MAXR 25005
#define LIM 450//~=sqrt(N)

int size[MAXN],tin[MAXN],tout[MAXN],r[MAXN],euler[MAXN];
vector<int> region[MAXR];//(tin)
vector<tuple<int,int,int>> blocks[MAXR];//(start,end,count)
int precomp[LIM][MAXR],id[MAXR];//for large regions
int cnt_large;

vector<int> ch[MAXN];//children
int dfs_timer;
int N,R,Q;

int dfs(int v){
    tin[v]=dfs_timer++;
    size[v]=1;
    euler[tin[v]]=v;
    region[r[v]].push_back(tin[v]);
    for(auto c:ch[v]){
        size[v]+=dfs(c);
    }
    tout[v]=tin[v]+size[v]-1;
    return size[v];
}

void prep(int re){//prepare region blocks
    vector<pair<int,int>> points;
    for(auto t:region[re]){
        points.push_back({t,0});//start
        points.push_back({tout[euler[t]],1});//end
    }
    int prev=0,cnt=0;
    sort(points.begin(),points.end());
    for(auto p:points){
        int pos=p.first;
        int type=p.second;
        if(type==0){
            //start
            if(pos!=prev){
                blocks[re].push_back({prev,pos-1,cnt});
            }
            cnt++;
            prev=pos;
        }else{
            //end
            blocks[re].push_back({prev,pos,cnt});
            cnt--;
            prev=pos+1;
        }
    }
}

void prep_large(int re){
    for(auto t:blocks[re]){
        int s,e,cnt;
        tie(s,e,cnt)=t;
        for(int i=s;i<=e;i++){
            int v=euler[i];
            if(r[v]==re) continue;
            precomp[id[re]][r[v]]+=cnt;
        }
    }
}

int query(int r1,int r2){//r1 is large
    int ans=0;
    for(auto t:region[r1]){
        int s=t;
        int e=tout[euler[t]];
        auto it1=lower_bound(region[r2].begin(),region[r2].end(),s);
        auto it2=upper_bound(region[r2].begin(),region[r2].end(),e);
        ans+=it2-it1;

    }
    return ans;
}

void init(){
    dfs(1);
    for(int re=1;re<=R;re++){
        prep(re);
        if(region[re].size()>LIM){
            id[re]=cnt_large++;
            prep_large(re);
        }
    }
}

int main(){
    scanf("%d%d%d",&N,&R,&Q);
    for(int v=1;v<=N;v++){
        if(v!=1){
            int p;
            scanf("%d",&p);
            ch[p].push_back(v);
        }
        scanf("%d",&r[v]);
    }
    init();
    for(int q=0;q<Q;q++){
        int r1,r2;
        scanf("%d%d",&r1,&r2);
        if(region[r1].size()>LIM){
            printf("%d\n",precomp[id[r1]][r2]);
        }else{
            printf("%d\n",query(r1,r2));
        }
        fflush(stdout);
    }
}

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

regions.cpp: In function 'int main()':
regions.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d%d%d",&N,&R,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d",&p);
      |             ~~~~~^~~~~~~~~
regions.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d",&r[v]);
      |         ~~~~~^~~~~~~~~~~~
regions.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d%d",&r1,&r2);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85