oj.uz

Submission #689603

# Submission time Handle Problem Language Result Execution time Memory
689603 2023-01-28T20:22:36 Z bane Regions (IOI09_regions) C++17
55 / 100
 3455 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() {
    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";
		cout.flush();
	  }
	  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';
		cout.flush();
	  }
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55712 KB Output is correct
2 Correct 22 ms 55764 KB Output is correct
3 Correct 23 ms 55760 KB Output is correct
4 Correct 26 ms 55716 KB Output is correct
5 Correct 27 ms 55760 KB Output is correct
6 Correct 41 ms 55920 KB Output is correct
7 Correct 50 ms 55860 KB Output is correct
8 Correct 49 ms 55948 KB Output is correct
9 Correct 75 ms 56404 KB Output is correct
10 Correct 100 ms 56264 KB Output is correct
11 Correct 130 ms 56616 KB Output is correct
12 Correct 143 ms 57284 KB Output is correct
13 Correct 175 ms 56784 KB Output is correct
14 Correct 254 ms 57416 KB Output is correct
15 Correct 290 ms 61276 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1454 ms 61588 KB Output isn't correct
2 Incorrect 1740 ms 59640 KB Output isn't correct
3 Incorrect 2641 ms 64720 KB Output isn't correct
4 Correct 240 ms 57552 KB Output is correct
5 Correct 376 ms 59936 KB Output is correct
6 Correct 900 ms 58964 KB Output is correct
7 Correct 1178 ms 59960 KB Output is correct
8 Correct 909 ms 66968 KB Output is correct
9 Correct 2041 ms 65804 KB Output is correct
10 Correct 3455 ms 72964 KB Output is correct
11 Correct 2845 ms 65288 KB Output is correct
12 Runtime error 165 ms 131072 KB Execution killed with signal 11
13 Runtime error 135 ms 131072 KB Execution killed with signal 11
14 Runtime error 158 ms 131072 KB Execution killed with signal 11
15 Runtime error 137 ms 131072 KB Execution killed with signal 11
16 Runtime error 166 ms 131072 KB Execution killed with signal 11
17 Runtime error 151 ms 131072 KB Execution killed with signal 11