oj.uz

Submission #199610

# Submission time Handle Problem Language Result Execution time Memory
199610 2020-02-02T08:38:15 Z songc Regions (IOI09_regions) C++14
0 / 100
 102 ms 26360 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, num, Q;
int qa[202020], qb[202020], C[202020], sz[202020], P[202020];
vector<int> S[202020], U[202020];
vector<int> adj[202020], cnt[202020];
map<pii,LL> ans;

void dfs(int u){
	int x=++num, a=C[u];
	cnt[a].push_back(x), P[a]++;
	for (int v : adj[u]) dfs(v);

	sort(S[a].begin(), S[a].end());
	S[a].erase(unique(S[a].begin(), S[a].end()), S[a].end());
	sort(U[a].begin(), U[a].end());
	U[a].erase(unique(U[a].begin(), U[a].end()), U[a].end());

	for (int b : S[a]) ans[pii(b, a)] += cnt[b].size()-(lower_bound(cnt[b].begin(), cnt[b].end(), x)-cnt[b].begin());
	for (int b : U[a]) ans[pii(a, b)] += P[b];

	P[a]--;
}

int main(){
	scanf("%d %*d %d", &N, &Q);
	scanf("%d", &C[1]);
	for (int i=2; i<=N; i++){
		int p;
		scanf("%d %d", &p, &C[i]);
		adj[p].push_back(i);
		sz[C[i]]++;
	}
	for (int i=1; i<=Q; i++){
		scanf("%d %d", &qb[i], &qa[i]);
		if (sz[qa[i]] < sz[qb[i]]) U[qa[i]].push_back(qb[i]);
		else S[qb[i]].push_back(qa[i]);
	}
	dfs(1);
	for (int i=1; i<=Q; i++) printf("%lld\n", ans[pii(qa[i], qb[i])]);
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %*d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C[1]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &qb[i], &qa[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 15 ms 19192 KB Time limit exceeded (wall clock)
2 Execution timed out 15 ms 19192 KB Time limit exceeded (wall clock)
3 Execution timed out 15 ms 19320 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 19320 KB Time limit exceeded (wall clock)
5 Execution timed out 16 ms 19320 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 19320 KB Time limit exceeded (wall clock)
7 Execution timed out 16 ms 19320 KB Time limit exceeded (wall clock)
8 Execution timed out 17 ms 19396 KB Time limit exceeded (wall clock)
9 Execution timed out 17 ms 19448 KB Time limit exceeded (wall clock)
10 Execution timed out 19 ms 19576 KB Time limit exceeded (wall clock)
11 Execution timed out 21 ms 19704 KB Time limit exceeded (wall clock)
12 Execution timed out 22 ms 19960 KB Time limit exceeded (wall clock)
13 Execution timed out 25 ms 19704 KB Time limit exceeded (wall clock)
14 Execution timed out 27 ms 20216 KB Time limit exceeded (wall clock)
15 Execution timed out 27 ms 20600 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 21752 KB Time limit exceeded (wall clock)
2 Execution timed out 41 ms 21112 KB Time limit exceeded (wall clock)
3 Execution timed out 43 ms 22392 KB Time limit exceeded (wall clock)
4 Execution timed out 27 ms 20216 KB Time limit exceeded (wall clock)
5 Execution timed out 26 ms 20600 KB Time limit exceeded (wall clock)
6 Execution timed out 33 ms 20856 KB Time limit exceeded (wall clock)
7 Execution timed out 39 ms 21372 KB Time limit exceeded (wall clock)
8 Execution timed out 51 ms 22776 KB Time limit exceeded (wall clock)
9 Execution timed out 66 ms 24184 KB Time limit exceeded (wall clock)
10 Execution timed out 76 ms 25288 KB Time limit exceeded (wall clock)
11 Execution timed out 102 ms 23800 KB Time limit exceeded (wall clock)
12 Execution timed out 84 ms 25900 KB Time limit exceeded (wall clock)
13 Execution timed out 85 ms 25336 KB Time limit exceeded (wall clock)
14 Execution timed out 96 ms 25208 KB Time limit exceeded (wall clock)
15 Execution timed out 87 ms 26360 KB Time limit exceeded (wall clock)
16 Execution timed out 85 ms 26360 KB Time limit exceeded (wall clock)
17 Execution timed out 85 ms 26324 KB Time limit exceeded (wall clock)