oj.uz

Submission #121466

# Submission time Handle Problem Language Result Execution time Memory
121466 2019-06-26T14:23:17 Z TadijaSebez Regions (IOI09_regions) C++11
90 / 100
 8000 ms 76664 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long int
const int N=200050;
const int S=205;
const int H=1050;
const int M=25050;
int sol[H][M];
int hid[M],reg[N],tsz;
vector<int> E[N],My[M],ids[M];
int lid[N],rid[N],tid;
void DFS(int u)
{
	lid[u]=++tid;
	ids[reg[u]].pb(tid);
	for(int i=0;i<E[u].size();i++) DFS(E[u][i]);
	rid[u]=tid;
}
void Heavy(int u, int r, int c)
{
	if(reg[u]==r) c++;
	else sol[hid[r]][reg[u]]+=c;
	for(int i=0;i<E[u].size();i++) Heavy(E[u][i],r,c);
}
int Get(int l, int r, int ty)
{
	return upper_bound(ids[ty].begin(),ids[ty].end(),r)-lower_bound(ids[ty].begin(),ids[ty].end(),l);
}
int par[N];
int main()
{
	int n,m,q,i;
	scanf("%i %i %i",&n,&m,&q);
	scanf("%i",&reg[1]);
	for(i=2;i<=n;i++) scanf("%i %i",&par[i],&reg[i]),E[par[i]].pb(i);
	for(i=1;i<=n;i++) My[reg[i]].pb(i);
	DFS(1);
	for(i=1;i<=m;i++) if(My[i].size()>=S) hid[i]=++tsz,Heavy(1,i,0);
	int x,y;
	while(q--)
	{
		scanf("%i %i",&x,&y);
		if(My[x].size()>=S) printf("%i\n",sol[hid[x]][y]);
		else
		{
			int ans=0;
			for(i=0;i<My[x].size();i++)
			{
				ans+=Get(lid[My[x][i]],rid[My[x][i]],y);
			}
			printf("%i\n",ans);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void DFS(int)':
regions.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) DFS(E[u][i]);
              ~^~~~~~~~~~~~
regions.cpp: In function 'void Heavy(int, int, int)':
regions.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) Heavy(E[u][i],r,c);
              ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<My[x].size();i++)
            ~^~~~~~~~~~~~~
regions.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&reg[1]);
  ~~~~~^~~~~~~~~~~~~~
regions.cpp:39:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=2;i<=n;i++) scanf("%i %i",&par[i],&reg[i]),E[par[i]].pb(i);
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
regions.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 11 ms 6144 KB Output is correct
5 Correct 15 ms 6144 KB Output is correct
6 Correct 20 ms 6272 KB Output is correct
7 Correct 34 ms 6272 KB Output is correct
8 Correct 23 ms 6400 KB Output is correct
9 Correct 44 ms 6656 KB Output is correct
10 Correct 78 ms 6784 KB Output is correct
11 Correct 138 ms 7040 KB Output is correct
12 Correct 158 ms 7552 KB Output is correct
13 Correct 224 ms 7296 KB Output is correct
14 Correct 273 ms 7936 KB Output is correct
15 Correct 239 ms 10508 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 11556 KB Output is correct
2 Correct 948 ms 10736 KB Output is correct
3 Correct 2906 ms 13096 KB Output is correct
4 Correct 177 ms 7940 KB Output is correct
5 Correct 188 ms 9200 KB Output is correct
6 Correct 417 ms 11192 KB Output is correct
7 Correct 915 ms 12540 KB Output is correct
8 Correct 822 ms 19796 KB Output is correct
9 Correct 2563 ms 22548 KB Output is correct
10 Correct 3156 ms 44560 KB Output is correct
11 Execution timed out 8093 ms 67736 KB Time limit exceeded
12 Execution timed out 8007 ms 31292 KB Time limit exceeded
13 Correct 4739 ms 33724 KB Output is correct
14 Correct 2849 ms 19676 KB Output is correct
15 Correct 3766 ms 22268 KB Output is correct
16 Correct 3316 ms 76664 KB Output is correct
17 Correct 3620 ms 28088 KB Output is correct