oj.uz

Submission #689613

# Submission time Handle Problem Language Result Execution time Memory
689613 2023-01-28T20:46:38 Z bane Regions (IOI09_regions) C++17
100 / 100
 3557 ms 75792 KB 
#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(NAX);
vector<int>H(NAX);
vector<int>adj[NAX];
vector<int>rs[25001];
int lend[NAX];
int ans[400][25005];
int tour[NAX];
int mapa[NAX], p[NAX];
int main() {
    scanf("%d%d%d", &N, &R, &Q);
    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<void(int, int, int)>Dfs2 = [&](int u, int r2, int brojac){
	  if (H[u] == r2)++brojac;
	  ans[p[r2]][H[u]]+=brojac;
	  for (int& x : adj[u]){
	    Dfs2(x, r2, brojac);
	  }
	};
	int c = 0;
	for(int i = 1; i<=R; i++){
	  sort(rs[i].begin(), rs[i].end());
	  if (rs[i].size() <= 500)continue;
	  p[i]=++c;
	  Dfs2(1,i,0);
	}
	while(Q--){
	  int a,b;
      cin >> a >> b;
	  if (rs[a].size() > 500){
		printf("%d\n", ans[p[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

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:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &H[1]);
      |     ~~~~~^~~~~~~~~~~~~
regions.cpp:22:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |    scanf("%d%d", &S[i], &H[i]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47824 KB Output is correct
2 Correct 20 ms 47908 KB Output is correct
3 Correct 22 ms 47824 KB Output is correct
4 Correct 22 ms 47824 KB Output is correct
5 Correct 24 ms 47824 KB Output is correct
6 Correct 37 ms 47996 KB Output is correct
7 Correct 48 ms 47916 KB Output is correct
8 Correct 56 ms 47948 KB Output is correct
9 Correct 60 ms 48536 KB Output is correct
10 Correct 100 ms 48376 KB Output is correct
11 Correct 83 ms 48688 KB Output is correct
12 Correct 161 ms 49240 KB Output is correct
13 Correct 169 ms 48752 KB Output is correct
14 Correct 182 ms 49304 KB Output is correct
15 Correct 254 ms 53036 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 52828 KB Output is correct
2 Correct 1911 ms 51048 KB Output is correct
3 Correct 2613 ms 55628 KB Output is correct
4 Correct 273 ms 49388 KB Output is correct
5 Correct 376 ms 51716 KB Output is correct
6 Correct 1222 ms 50640 KB Output is correct
7 Correct 1561 ms 51488 KB Output is correct
8 Correct 1014 ms 58264 KB Output is correct
9 Correct 2079 ms 56696 KB Output is correct
10 Correct 3557 ms 63600 KB Output is correct
11 Correct 3312 ms 55720 KB Output is correct
12 Correct 1223 ms 57528 KB Output is correct
13 Correct 1811 ms 58468 KB Output is correct
14 Correct 2278 ms 57632 KB Output is correct
15 Correct 2876 ms 64684 KB Output is correct
16 Correct 2803 ms 75792 KB Output is correct
17 Correct 2928 ms 73540 KB Output is correct