Submission #689600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
689600	2023-01-28T20:17:43 Z	bane	Regions (IOI09_regions)	C++17	0 / 100	167 ms	131072 KB

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[nax][25001];
int tour[NAX];
int mapa[NAX];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N >> R >> Q;
    S.resize(N + 1);
    H.resize(N + 1);
    cin >> H[1];
    for (int i = 2; i<=N; i++){
	  cin >> 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)cout<<ans[a][b]<<'\n';
	  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);
		} 
		cout<<tot<<'\n';
	  }
	}
	return 0;
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	25 ms	55744 KB	Time limit exceeded (wall clock)
2	Execution timed out	25 ms	55736 KB	Time limit exceeded (wall clock)
3	Execution timed out	24 ms	55752 KB	Time limit exceeded (wall clock)
4	Execution timed out	26 ms	55760 KB	Time limit exceeded (wall clock)
5	Execution timed out	27 ms	55752 KB	Time limit exceeded (wall clock)
6	Execution timed out	24 ms	55888 KB	Time limit exceeded (wall clock)
7	Execution timed out	28 ms	55892 KB	Time limit exceeded (wall clock)
8	Execution timed out	25 ms	55868 KB	Time limit exceeded (wall clock)
9	Execution timed out	26 ms	56472 KB	Time limit exceeded (wall clock)
10	Execution timed out	27 ms	56388 KB	Time limit exceeded (wall clock)
11	Execution timed out	32 ms	56648 KB	Time limit exceeded (wall clock)
12	Execution timed out	29 ms	57312 KB	Time limit exceeded (wall clock)
13	Execution timed out	34 ms	56780 KB	Time limit exceeded (wall clock)
14	Execution timed out	31 ms	57416 KB	Time limit exceeded (wall clock)
15	Execution timed out	34 ms	61244 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	69 ms	61512 KB	Time limit exceeded (wall clock)
2	Execution timed out	81 ms	59596 KB	Time limit exceeded (wall clock)
3	Execution timed out	62 ms	64632 KB	Time limit exceeded (wall clock)
4	Execution timed out	36 ms	57448 KB	Time limit exceeded (wall clock)
5	Execution timed out	36 ms	59848 KB	Time limit exceeded (wall clock)
6	Execution timed out	38 ms	58952 KB	Time limit exceeded (wall clock)
7	Execution timed out	54 ms	59932 KB	Time limit exceeded (wall clock)
8	Execution timed out	50 ms	66920 KB	Time limit exceeded (wall clock)
9	Execution timed out	82 ms	65696 KB	Time limit exceeded (wall clock)
10	Execution timed out	73 ms	72752 KB	Time limit exceeded (wall clock)
11	Execution timed out	87 ms	65132 KB	Time limit exceeded (wall clock)
12	Runtime error	156 ms	131072 KB	Execution killed with signal 11
13	Runtime error	141 ms	131072 KB	Execution killed with signal 11
14	Runtime error	158 ms	131072 KB	Execution killed with signal 11
15	Runtime error	151 ms	131072 KB	Execution killed with signal 11
16	Runtime error	167 ms	131072 KB	Execution killed with signal 11
17	Runtime error	156 ms	131072 KB	Execution killed with signal 11