oj.uz

Submission #689609

# Submission time Handle Problem Language Result Execution time Memory
689609 2023-01-28T20:40:22 Z bane Regions (IOI09_regions) C++17
55 / 100
 3491 ms 131072 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;
vector<int>H;
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);
    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<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[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: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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45928 KB Output is correct
2 Correct 18 ms 45836 KB Output is correct
3 Correct 18 ms 45824 KB Output is correct
4 Correct 21 ms 45896 KB Output is correct
5 Correct 30 ms 45868 KB Output is correct
6 Correct 36 ms 46000 KB Output is correct
7 Correct 40 ms 46020 KB Output is correct
8 Correct 51 ms 46012 KB Output is correct
9 Correct 61 ms 46520 KB Output is correct
10 Correct 82 ms 46416 KB Output is correct
11 Correct 125 ms 46800 KB Output is correct
12 Correct 143 ms 47436 KB Output is correct
13 Correct 179 ms 46920 KB Output is correct
14 Correct 237 ms 47484 KB Output is correct
15 Correct 254 ms 51396 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1704 ms 51464 KB Output isn't correct
2 Incorrect 1688 ms 49720 KB Output isn't correct
3 Incorrect 2327 ms 54280 KB Output isn't correct
4 Correct 293 ms 47560 KB Output is correct
5 Correct 378 ms 50048 KB Output is correct
6 Correct 1027 ms 49080 KB Output is correct
7 Correct 1414 ms 50080 KB Output is correct
8 Correct 1077 ms 57080 KB Output is correct
9 Correct 1923 ms 55912 KB Output is correct
10 Correct 3491 ms 62976 KB Output is correct
11 Correct 3269 ms 55340 KB Output is correct
12 Runtime error 181 ms 115416 KB Execution killed with signal 11
13 Runtime error 170 ms 117472 KB Execution killed with signal 11
14 Runtime error 447 ms 115892 KB Execution killed with signal 11
15 Runtime error 153 ms 130156 KB Execution killed with signal 11
16 Runtime error 174 ms 131072 KB Execution killed with signal 11
17 Runtime error 261 ms 131072 KB Execution killed with signal 11