oj.uz

Submission #299084

# Submission time Handle Problem Language Result Execution time Memory
299084 2020-09-14T13:11:39 Z TadijaSebez Regions (IOI09_regions) C++11
100 / 100
 3385 ms 54136 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 12 ms 14464 KB Output is correct
4 Correct 15 ms 14464 KB Output is correct
5 Correct 18 ms 14464 KB Output is correct
6 Correct 19 ms 14464 KB Output is correct
7 Correct 36 ms 14592 KB Output is correct
8 Correct 40 ms 14592 KB Output is correct
9 Correct 62 ms 15104 KB Output is correct
10 Correct 131 ms 15104 KB Output is correct
11 Correct 161 ms 15488 KB Output is correct
12 Correct 146 ms 16128 KB Output is correct
13 Correct 211 ms 16000 KB Output is correct
14 Correct 230 ms 16760 KB Output is correct
15 Correct 236 ms 19320 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 20592 KB Output is correct
2 Correct 1044 ms 19472 KB Output is correct
3 Correct 1714 ms 22440 KB Output is correct
4 Correct 267 ms 16640 KB Output is correct
5 Correct 342 ms 18304 KB Output is correct
6 Correct 806 ms 25208 KB Output is correct
7 Correct 1150 ms 22396 KB Output is correct
8 Correct 1651 ms 41464 KB Output is correct
9 Correct 1552 ms 27000 KB Output is correct
10 Correct 2834 ms 54136 KB Output is correct
11 Correct 2373 ms 27240 KB Output is correct
12 Correct 1445 ms 28664 KB Output is correct
13 Correct 2069 ms 28852 KB Output is correct
14 Correct 2981 ms 35612 KB Output is correct
15 Correct 2971 ms 33736 KB Output is correct
16 Correct 2758 ms 38532 KB Output is correct
17 Correct 3385 ms 44428 KB Output is correct