oj.uz

Submission #348784

# Submission time Handle Problem Language Result Execution time Memory
348784 2021-01-15T17:19:53 Z Mefarnis Regions (IOI09_regions) C++14
30 / 100
 1283 ms 25836 KB 
#include <bits/stdc++.h>
#define maxm 501
#define maxM 25001
#define maxn 200001
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;

int n,m,q,t;
int dad[maxn];
int group[maxn];
int chain[maxm];
int res[maxm][maxm];
vector<int> dts[maxM];
vector<int> fts[maxM];
vector<int> adj[maxn];

void dfs2(int u) {
	t++;
	int deg = adj[u].size();
	dts[group[u]].pb(t);
	for( int i = 0 ; i < deg ; i++ )
		dfs2(adj[u][i]);
	fts[group[u]].pb(t);
}

void dfs1(int u) {
	int deg = adj[u].size();
	for( int i = 1 ; i <= m ; i++ )
		res[i][group[u]] += chain[i];
	chain[group[u]]++;
	for( int i = 0 ; i < deg ; i++ )
		dfs1(adj[u][i]);
	chain[group[u]]--;
}

int main() {
	scanf("%d%d%d",&n,&m,&q);
	scanf("%d",&group[1]);
	for( int i = 2 ; i <= n ; i++ ) {
		scanf("%d%d",&dad[i],&group[i]);
		adj[dad[i]].pb(i);
	}
	if(m < maxm) {
		dfs1(1);
		for( int i = 0 , x,y ; i < q ; i++ ) {
			scanf("%d%d",&x,&y);
			printf("%d\n",res[x][y]);
			fflush(stdout);
		}
	}
	else {
		dfs2(1);
		
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d",&group[1]);
      |  ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d%d",&dad[i],&group[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:48:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 5 ms 6252 KB Output is correct
3 Correct 6 ms 6252 KB Output is correct
4 Correct 8 ms 6252 KB Output is correct
5 Correct 8 ms 6252 KB Output is correct
6 Correct 22 ms 6784 KB Output is correct
7 Correct 21 ms 6508 KB Output is correct
8 Correct 35 ms 6636 KB Output is correct
9 Correct 32 ms 7276 KB Output is correct
10 Correct 78 ms 7404 KB Output is correct
11 Correct 92 ms 7404 KB Output is correct
12 Correct 85 ms 8172 KB Output is correct
13 Correct 130 ms 7404 KB Output is correct
14 Correct 146 ms 7660 KB Output is correct
15 Correct 190 ms 10732 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 10400 KB Output is correct
2 Correct 1026 ms 9088 KB Output is correct
3 Correct 1283 ms 12396 KB Output is correct
4 Incorrect 19 ms 7804 KB Unexpected end of file - int32 expected
5 Incorrect 18 ms 9324 KB Unexpected end of file - int32 expected
6 Incorrect 26 ms 8940 KB Unexpected end of file - int32 expected
7 Incorrect 35 ms 9964 KB Unexpected end of file - int32 expected
8 Incorrect 48 ms 14732 KB Unexpected end of file - int32 expected
9 Incorrect 75 ms 15064 KB Unexpected end of file - int32 expected
10 Incorrect 75 ms 19948 KB Unexpected end of file - int32 expected
11 Incorrect 98 ms 14756 KB Unexpected end of file - int32 expected
12 Incorrect 103 ms 16108 KB Unexpected end of file - int32 expected
13 Incorrect 100 ms 16368 KB Unexpected end of file - int32 expected
14 Incorrect 106 ms 16108 KB Unexpected end of file - int32 expected
15 Incorrect 89 ms 20588 KB Unexpected end of file - int32 expected
16 Incorrect 94 ms 25836 KB Unexpected end of file - int32 expected
17 Incorrect 86 ms 24684 KB Unexpected end of file - int32 expected