Submission #199610

#	Time	Username	Problem	Language	Result	Execution time	Memory
199610		songc	Regions (IOI09_regions)	C++14	0 / 100	102 ms	26360 KiB

regions

#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 (stderr)

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
• Subtask 2: 0 / 85