oj.uz

Submission #348787

# Submission time Handle Problem Language Result Execution time Memory
348787 2021-01-15T17:30:49 Z Mefarnis Regions (IOI09_regions) C++14
95 / 100
 8000 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 tc = 0 , x,y ; tc < q ; tc++ ) {
			scanf("%d%d",&x,&y);
			printf("%d\n",res[x][y]);
			fflush(stdout);
		}
	}
	else {
		dfs2(1);
		for( int tc = 0 , x,y ; tc < q ; tc++ ) {
			scanf("%d%d",&x,&y);
			int add = 0 , ans = 0;
			int i = 0 , j = 0 , k = 0;
			int szx = dts[x].size();
			int szy = dts[y].size();
			while(i < szx || j < szx || k < szy) {
				int a = (i < szx) ? dts[x][i] : INT_MAX;
				int b = (j < szx) ? fts[x][j] : INT_MAX;
				int c = (k < szy) ? dts[y][k] : INT_MAX;
				int mn = min(min(a,b),c);
				if(c == mn)
					ans += add , k++;
				else if(a == mn)
					add++ , i++;
				else if(b == mn)
					add-- , j++;
			}
			printf("%d\n",ans);
			fflush(stdout);
		}
	}
	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);
      |    ~~~~~^~~~~~~~~~~~~~
regions.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |    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 4 ms 6252 KB Output is correct
3 Correct 6 ms 6252 KB Output is correct
4 Correct 7 ms 6252 KB Output is correct
5 Correct 10 ms 6252 KB Output is correct
6 Correct 19 ms 6764 KB Output is correct
7 Correct 40 ms 6508 KB Output is correct
8 Correct 53 ms 6636 KB Output is correct
9 Correct 49 ms 7276 KB Output is correct
10 Correct 73 ms 7404 KB Output is correct
11 Correct 146 ms 7296 KB Output is correct
12 Correct 147 ms 8172 KB Output is correct
13 Correct 182 ms 7532 KB Output is correct
14 Correct 152 ms 7660 KB Output is correct
15 Correct 257 ms 10880 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 10348 KB Output is correct
2 Correct 965 ms 8940 KB Output is correct
3 Correct 1314 ms 12396 KB Output is correct
4 Correct 324 ms 7788 KB Output is correct
5 Correct 346 ms 9324 KB Output is correct
6 Correct 918 ms 8940 KB Output is correct
7 Correct 1254 ms 10028 KB Output is correct
8 Correct 1143 ms 14700 KB Output is correct
9 Correct 1797 ms 15212 KB Output is correct
10 Correct 2568 ms 19948 KB Output is correct
11 Correct 3018 ms 14828 KB Output is correct
12 Correct 5061 ms 16216 KB Output is correct
13 Correct 6054 ms 16364 KB Output is correct
14 Execution timed out 8051 ms 16108 KB Time limit exceeded
15 Correct 7103 ms 20652 KB Output is correct
16 Correct 7832 ms 25836 KB Output is correct
17 Correct 6916 ms 24556 KB Output is correct