Submission #299084

#	Time	Username	Problem	Language	Result	Execution time	Memory
299084		TadijaSebez	Regions (IOI09_regions)	C++11	100 / 100	3385 ms	54136 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int R=25000;
const int S=447;
const int H=N/S+1;
#define ll long long
ll up[H][R],dw[H][R];
int cnt[R],my[N],idx[N],lid[N],rid[N],sz[R],tid,n,r,q;
#define pb push_back
#define pii pair<int,int>
vector<int> E[N],heavy,pts[N];
vector<pii> sw[N];
void DFS(int u){
	if(idx[my[u]]){
		for(int i=1;i<=r;i++)dw[idx[my[u]]-1][i]+=cnt[i];
	}
	for(int i:heavy)up[idx[i]-1][my[u]]+=cnt[i];
	cnt[my[u]]++;
	lid[u]=++tid;
	sw[my[u]].pb({tid-1,-1});
	pts[my[u]].pb(tid);
	for(int v:E[u])DFS(v);
	rid[u]=tid;
	sw[my[u]].pb({tid,1});
	cnt[my[u]]--;
}
int main(){
	scanf("%i %i %i",&n,&r,&q);
	for(int i=1;i<=n;i++){
		int par;if(i!=1)scanf("%i",&par),E[par].pb(i);
		scanf("%i",&my[i]);
		sz[my[i]]++;
	}
	for(int i=1;i<=r;i++)if(sz[i]>S)heavy.pb(i),idx[i]=heavy.size();
	DFS(1);
	while(q--){
		int r1,r2;
		scanf("%i %i",&r1,&r2);
		if(idx[r1])printf("%lld\n",up[idx[r1]-1][r2]);
		else if(idx[r2])printf("%lld\n",dw[idx[r2]-1][r1]);
		else{
			int ans=0;
			for(int i=0,j=0;i<sw[r1].size();i++){
				while(j<pts[r2].size()&&pts[r2][j]<=sw[r1][i].first)j++;
				ans+=j*sw[r1][i].second;
			}
			printf("%i\n",ans);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int i=0,j=0;i<sw[r1].size();i++){
      |                    ~^~~~~~~~~~~~~~
regions.cpp:45:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(j<pts[r2].size()&&pts[r2][j]<=sw[r1][i].first)j++;
      |           ~^~~~~~~~~~~~~~~
regions.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%i %i %i",&n,&r,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   int par;if(i!=1)scanf("%i",&par),E[par].pb(i);
      |                   ~~~~~^~~~~~~~~~~
regions.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%i",&my[i]);
      |   ~~~~~^~~~~~~~~~~~~
regions.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%i %i",&r1,&r2);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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