Submission #431779

#TimeUsernameProblemLanguageResultExecution timeMemory
431779KerimRegions (IOI09_regions)C++17
100 / 100
5760 ms106412 KiB
#include "bits/stdc++.h" #define MAXN 200009 #define INF 1000000007 #define mp(x,y) make_pair(x,y) #define all(v) v.begin(),v.end() #define pb(x) push_back(x) #define wr cout<<"----------------"<<endl; #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define ff first #define ss second #define my_little_dodge 46 #define debug(x) cerr<< #x <<" = "<< x<<endl; using namespace std; typedef long long ll; typedef pair<int,int> PII; template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int C=25009; const int K=300; const int N=2e5+5; int id[MAXN],idx,a[MAXN]; vector<int>adj[MAXN]; vector<PII>comp[MAXN]; int who[MAXN],mx[MAXN],who_color[MAXN]; int cnt[MAXN],sub[MAXN]; int bs[N/K+3][C]; int heavy[MAXN]; int sb[C][N/K+3]; int tin[MAXN],tout[MAXN],T; void pre(int nd=1){ tin[nd]=++T; sub[nd]=1; for(auto to:adj[nd]){ pre(to); sub[nd]+=sub[to]; if(umax(mx[nd],sub[to])) who[nd]=to; } tout[nd]=T; } //bb, bs void dfs0(int color_id,int nd=1,int cnt_black=0){ bs[color_id][a[nd]]+=cnt_black; cnt_black+=(~id[a[nd]] and id[a[nd]]==color_id); for(auto to:adj[nd]) dfs0(color_id,to,cnt_black); } //sb void add(int nd){ cnt[a[nd]]++; for(auto to:adj[nd]) add(to); } void rem(int nd){ cnt[a[nd]]--; for(auto to:adj[nd]) rem(to); } void dfs1(int nd=1,int keep=1){ for(auto to:adj[nd]) if(to!=who[nd]) dfs1(to,0); if(who[nd]) dfs1(who[nd],1); for(auto to:adj[nd]) if(to!=who[nd]) add(to); cnt[a[nd]]++; //here you have all color's cnt of my subtree for(int c=0;c<idx;c++) sb[a[nd]][c]+=cnt[who_color[c]]; if(!keep) rem(nd); } int ata(int x,int y){ return (tin[x]<=tin[y] and tout[y]<=tout[x]); } bool is_heavy(int x){ return (int(comp[x].size())>K); } //log(S_i<K)~=8 int get(int x,PII tmp){ int a=lower_bound(all(comp[x]),mp(tmp.ff,-1))-comp[x].begin(); int b=upper_bound(all(comp[x]),mp(tmp.ss,INF))-comp[x].begin(); return b-a; } int main(){ //~ freopen("file.in", "r", stdin); int n,c,q; scanf("%d%d%d",&n,&c,&q); scanf("%d",&a[1]); for(int i=2;i<=n;i++){ int p; scanf("%d%d",&p,&a[i]); adj[p].pb(i); } pre(); for(int i=1;i<=n;i++) comp[a[i]].pb(mp(tin[i],tout[i])); idx=0; for(int i=1;i<=c;i++){ sort(all(comp[i])); if(is_heavy(i)){ who_color[idx]=i; id[i]=idx++; } else id[i]=-1; } for(int i=0;i<idx;i++) dfs0(i); dfs1(); ll res; while(q--){ int a,b; scanf("%d%d",&a,&b); assert(a!=b); if(~id[a]) printf("%d\n",bs[id[a]][b]); else if(~id[b]) printf("%d\n",sb[a][id[b]]); else{ //ss res=0; for(int i=0;i<int(comp[a].size());i++) res+=get(b,comp[a][i]); printf("%lld\n",res); } fflush(stdout); } return 0; }

Compilation message (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,&c,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d",&a[1]);
      |     ~~~~~^~~~~~~~~~~~
regions.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d%d",&p,&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...