Submission #689608

#	Time	Username	Problem	Language	Result	Execution time	Memory
689608		bane	Regions (IOI09_regions)	C++17	13 / 100	8100 ms	131072 KiB

regions

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int nax = 501;
const int NAX = 500*500 + 1;
int N,R,Q;
vector<int>S;
vector<int>H;
vector<int>adj[NAX];
vector<int>rs[25001];
int lend[NAX];
int ans[400][25005];
int tour[NAX];
int mapa[NAX];
int main() {
    scanf("%d%d%d", &N, &R, &Q);
    S.resize(N + 1);
    H.resize(N + 1);
    scanf("%d", &H[1]);
    for (int i = 2; i<=N; i++){
	  scanf("%d%d", &S[i], &H[i]);
	  adj[S[i]].pb(i);
	}
	int timer = 0;
	function<void(int)>Dfs = [&](int u){
	  lend[u]=timer++;
	  mapa[timer-1] = u;
	  for (int& x : adj[u])Dfs(x);
	  rs[H[u]].pb(lend[u]);
	  tour[u]=timer-1;
	};
	Dfs(1);
	memset(ans, 0, sizeof(ans));
	function<int(int, int, int)>Dfs2 = [&](int u, int r2, int brojac){
	  int cnt = 0;
	  for (int& x : adj[u]){
	    cnt+=Dfs2(x, r2, brojac);
	  }
	  if (H[u] == r2)++cnt;
	  ans[H[u]][r2]+=cnt;
	  return cnt;
	};
	for(int i = 1; i<=R; i++){
	  sort(rs[i].begin(), rs[i].end());
	 // if (rs[i].size() <= 500)continue;
	  Dfs2(1,i,0);
	}
	while(Q--){
	  int a,b;
      cin >> a >> b;
	  if (rs[a].size() <= 500){
		printf("%d\n", ans[a][b]);
		fflush(stdout);
	  }
	  else{
	    int tot = 0;
	    for(int i = 0; i < (int)rs[a].size(); i++){
	      int l = rs[a][i];
	      int r = tour[mapa[l]];
	      int it1 = lower_bound(rs[b].begin(), rs[b].end(), l) - rs[b].begin();
	      int it2 = lower_bound(rs[b].begin(), rs[b].end(), r+1) - rs[b].begin();
	      tot+=(it2 - it1);
		} 
		printf("%d\n", tot);
		fflush(stdout);
	  }
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d%d", &N, &R, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d", &H[1]);
      |     ~~~~~^~~~~~~~~~~~~
regions.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |    scanf("%d%d", &S[i], &H[i]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 15
• Subtask 2: 0 / 85