oj.uz

Submission #348786

# Submission time Handle Problem Language Result Execution time Memory
348786 2021-01-15T17:30:10 Z Mefarnis Regions (IOI09_regions) C++14
25 / 100
 8000 ms 30316 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 7 ms 6252 KB Output is correct
4 Correct 10 ms 6252 KB Output is correct
5 Correct 13 ms 6252 KB Output is correct
6 Correct 19 ms 6252 KB Output is correct
7 Correct 29 ms 6252 KB Output is correct
8 Correct 35 ms 6380 KB Output is correct
9 Correct 50 ms 6692 KB Output is correct
10 Correct 81 ms 6764 KB Output is correct
11 Correct 114 ms 7020 KB Output is correct
12 Correct 92 ms 7532 KB Output is correct
13 Correct 163 ms 7148 KB Output is correct
14 Correct 173 ms 7680 KB Output is correct
15 Correct 231 ms 10220 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4436 ms 10624 KB Output is correct
2 Execution timed out 8086 ms 9452 KB Time limit exceeded
3 Correct 6215 ms 12380 KB Output is correct
4 Runtime error 25 ms 19308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 30 ms 20076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 35 ms 20460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 21484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 48 ms 24172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 65 ms 26604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 79 ms 28268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 76 ms 24940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 75 ms 29420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 75 ms 28392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 77 ms 28012 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 78 ms 30316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 78 ms 30188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 90 ms 30200 KB Execution killed with signal 11 (could be triggered by violating memory limits)