oj.uz

Submission #121472

# Submission time Handle Problem Language Result Execution time Memory
121472 2019-06-26T14:25:24 Z TadijaSebez Regions (IOI09_regions) C++11
90 / 100
 8000 ms 76644 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 7 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 7 ms 6108 KB Output is correct
4 Correct 9 ms 6144 KB Output is correct
5 Correct 13 ms 6192 KB Output is correct
6 Correct 24 ms 6272 KB Output is correct
7 Correct 33 ms 6272 KB Output is correct
8 Correct 20 ms 6400 KB Output is correct
9 Correct 53 ms 6656 KB Output is correct
10 Correct 74 ms 6784 KB Output is correct
11 Correct 120 ms 7040 KB Output is correct
12 Correct 126 ms 7424 KB Output is correct
13 Correct 172 ms 7296 KB Output is correct
14 Correct 297 ms 7808 KB Output is correct
15 Correct 281 ms 10488 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 11516 KB Output is correct
2 Correct 908 ms 10748 KB Output is correct
3 Correct 3194 ms 13028 KB Output is correct
4 Correct 220 ms 7936 KB Output is correct
5 Correct 352 ms 9208 KB Output is correct
6 Correct 313 ms 11184 KB Output is correct
7 Correct 1174 ms 12560 KB Output is correct
8 Correct 1160 ms 19784 KB Output is correct
9 Correct 3094 ms 22604 KB Output is correct
10 Correct 3914 ms 44564 KB Output is correct
11 Execution timed out 8099 ms 68796 KB Time limit exceeded
12 Execution timed out 8007 ms 31260 KB Time limit exceeded
13 Correct 4024 ms 33580 KB Output is correct
14 Correct 3105 ms 19552 KB Output is correct
15 Correct 3696 ms 22280 KB Output is correct
16 Correct 3473 ms 76644 KB Output is correct
17 Correct 3823 ms 28060 KB Output is correct