oj.uz

Submission #689607

# Submission time Handle Problem Language Result Execution time Memory
689607 2023-01-28T20:27:34 Z bane Regions (IOI09_regions) C++17
55 / 100
 3498 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[nax][25001];
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

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 21 ms 55704 KB Output is correct
2 Correct 21 ms 55756 KB Output is correct
3 Correct 25 ms 55788 KB Output is correct
4 Correct 28 ms 55740 KB Output is correct
5 Correct 30 ms 55800 KB Output is correct
6 Correct 40 ms 55904 KB Output is correct
7 Correct 54 ms 55828 KB Output is correct
8 Correct 57 ms 55888 KB Output is correct
9 Correct 61 ms 56400 KB Output is correct
10 Correct 74 ms 56272 KB Output is correct
11 Correct 142 ms 56652 KB Output is correct
12 Correct 162 ms 57296 KB Output is correct
13 Correct 113 ms 56788 KB Output is correct
14 Correct 263 ms 57416 KB Output is correct
15 Correct 264 ms 61272 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1558 ms 61568 KB Output isn't correct
2 Incorrect 1949 ms 59620 KB Output isn't correct
3 Incorrect 2706 ms 64700 KB Output isn't correct
4 Correct 280 ms 57416 KB Output is correct
5 Correct 420 ms 59916 KB Output is correct
6 Correct 1154 ms 58952 KB Output is correct
7 Correct 1510 ms 59944 KB Output is correct
8 Correct 1144 ms 66956 KB Output is correct
9 Correct 1975 ms 65780 KB Output is correct
10 Correct 3498 ms 72836 KB Output is correct
11 Correct 3312 ms 65192 KB Output is correct
12 Runtime error 156 ms 131072 KB Execution killed with signal 11
13 Runtime error 144 ms 131072 KB Execution killed with signal 11
14 Runtime error 154 ms 131072 KB Execution killed with signal 11
15 Runtime error 145 ms 131072 KB Execution killed with signal 11
16 Runtime error 195 ms 131072 KB Execution killed with signal 11
17 Runtime error 165 ms 131072 KB Execution killed with signal 11