oj.uz

Submission #121477

# Submission time Handle Problem Language Result Execution time Memory
121477 2019-06-26T14:28:38 Z TadijaSebez Regions (IOI09_regions) C++11
95 / 100
 8000 ms 76800 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=220;
const int H=1060;
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 6272 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 9 ms 6272 KB Output is correct
4 Correct 11 ms 6316 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 24 ms 6272 KB Output is correct
7 Correct 17 ms 6272 KB Output is correct
8 Correct 31 ms 6272 KB Output is correct
9 Correct 43 ms 6632 KB Output is correct
10 Correct 79 ms 6784 KB Output is correct
11 Correct 109 ms 7040 KB Output is correct
12 Correct 151 ms 7472 KB Output is correct
13 Correct 159 ms 7212 KB Output is correct
14 Correct 350 ms 7896 KB Output is correct
15 Correct 326 ms 9848 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1802 ms 11308 KB Output is correct
2 Correct 1378 ms 10872 KB Output is correct
3 Correct 3175 ms 13036 KB Output is correct
4 Correct 171 ms 8064 KB Output is correct
5 Correct 422 ms 9208 KB Output is correct
6 Correct 605 ms 11212 KB Output is correct
7 Correct 1227 ms 12644 KB Output is correct
8 Correct 1539 ms 19808 KB Output is correct
9 Correct 3473 ms 22604 KB Output is correct
10 Correct 3773 ms 31144 KB Output is correct
11 Execution timed out 8037 ms 67152 KB Time limit exceeded
12 Correct 2153 ms 17736 KB Output is correct
13 Correct 2502 ms 19248 KB Output is correct
14 Correct 3215 ms 19628 KB Output is correct
15 Correct 4208 ms 22268 KB Output is correct
16 Correct 3328 ms 76800 KB Output is correct
17 Correct 3815 ms 28096 KB Output is correct