oj.uz

Submission #689608

# Submission time Handle Problem Language Result Execution time Memory
689608 2023-01-28T20:30:48 Z bane Regions (IOI09_regions) C++17
13 / 100
 8000 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];
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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45904 KB Output is correct
2 Correct 18 ms 45892 KB Output is correct
3 Correct 18 ms 45856 KB Output is correct
4 Correct 19 ms 45840 KB Output is correct
5 Correct 24 ms 45904 KB Output is correct
6 Correct 37 ms 46004 KB Output is correct
7 Correct 44 ms 45956 KB Output is correct
8 Correct 55 ms 46032 KB Output is correct
9 Correct 77 ms 46752 KB Output is correct
10 Runtime error 63 ms 94064 KB Execution killed with signal 11
11 Correct 217 ms 46828 KB Output is correct
12 Execution timed out 8100 ms 47824 KB Time limit exceeded
13 Correct 422 ms 46948 KB Output is correct
14 Correct 374 ms 47560 KB Output is correct
15 Correct 395 ms 52644 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 51684 KB Time limit exceeded
2 Execution timed out 8083 ms 49740 KB Time limit exceeded
3 Execution timed out 8067 ms 54812 KB Time limit exceeded
4 Runtime error 76 ms 96400 KB Execution killed with signal 11
5 Runtime error 71 ms 101244 KB Execution killed with signal 11
6 Runtime error 83 ms 99272 KB Execution killed with signal 11
7 Runtime error 82 ms 101328 KB Execution killed with signal 11
8 Runtime error 94 ms 115424 KB Execution killed with signal 11
9 Runtime error 119 ms 113276 KB Execution killed with signal 11
10 Runtime error 123 ms 127408 KB Execution killed with signal 11
11 Runtime error 129 ms 111952 KB Execution killed with signal 11
12 Runtime error 150 ms 115292 KB Execution killed with signal 11
13 Runtime error 129 ms 116760 KB Execution killed with signal 11
14 Runtime error 137 ms 115424 KB Execution killed with signal 11
15 Runtime error 139 ms 127848 KB Execution killed with signal 11
16 Runtime error 159 ms 131072 KB Execution killed with signal 11
17 Runtime error 149 ms 131072 KB Execution killed with signal 11