oj.uz

Submission #427418

# Submission time Handle Problem Language Result Execution time Memory
427418 2021-06-14T15:04:08 Z pliam Regions (IOI09_regions) C++14
100 / 100
 5978 ms 33596 KB 
#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);
    }
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6216 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6176 KB Output is correct
4 Correct 10 ms 6088 KB Output is correct
5 Correct 15 ms 6216 KB Output is correct
6 Correct 32 ms 6216 KB Output is correct
7 Correct 34 ms 6216 KB Output is correct
8 Correct 40 ms 6344 KB Output is correct
9 Correct 82 ms 6856 KB Output is correct
10 Correct 97 ms 6984 KB Output is correct
11 Correct 141 ms 7440 KB Output is correct
12 Correct 200 ms 8136 KB Output is correct
13 Correct 267 ms 8044 KB Output is correct
14 Correct 294 ms 9032 KB Output is correct
15 Correct 299 ms 11840 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2040 ms 13548 KB Output is correct
2 Correct 1960 ms 12568 KB Output is correct
3 Correct 2932 ms 15412 KB Output is correct
4 Correct 306 ms 8904 KB Output is correct
5 Correct 413 ms 10648 KB Output is correct
6 Correct 628 ms 12480 KB Output is correct
7 Correct 1719 ms 12996 KB Output is correct
8 Correct 1329 ms 22416 KB Output is correct
9 Correct 2777 ms 21144 KB Output is correct
10 Correct 4822 ms 30644 KB Output is correct
11 Correct 5978 ms 21600 KB Output is correct
12 Correct 1829 ms 22712 KB Output is correct
13 Correct 2406 ms 22932 KB Output is correct
14 Correct 2559 ms 24956 KB Output is correct
15 Correct 3899 ms 28008 KB Output is correct
16 Correct 3876 ms 32320 KB Output is correct
17 Correct 3376 ms 33596 KB Output is correct