oj.uz

답안 #689605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689605 2023-01-28T20:25:14 Z bane Regions (IOI09_regions) C++17
0 / 100
 175 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';
		fflush(stdout);
	  }
	}
	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 23 ms 55696 KB Time limit exceeded (wall clock)
2 Execution timed out 26 ms 55788 KB Time limit exceeded (wall clock)
3 Execution timed out 23 ms 55696 KB Time limit exceeded (wall clock)
4 Execution timed out 23 ms 55888 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 55824 KB Time limit exceeded (wall clock)
6 Execution timed out 27 ms 55852 KB Time limit exceeded (wall clock)
7 Execution timed out 23 ms 55880 KB Time limit exceeded (wall clock)
8 Execution timed out 28 ms 55896 KB Time limit exceeded (wall clock)
9 Execution timed out 25 ms 56528 KB Time limit exceeded (wall clock)
10 Execution timed out 25 ms 56324 KB Time limit exceeded (wall clock)
11 Execution timed out 27 ms 56664 KB Time limit exceeded (wall clock)
12 Execution timed out 29 ms 57296 KB Time limit exceeded (wall clock)
13 Execution timed out 29 ms 56784 KB Time limit exceeded (wall clock)
14 Execution timed out 41 ms 57440 KB Time limit exceeded (wall clock)
15 Execution timed out 34 ms 61248 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 67 ms 61588 KB Time limit exceeded (wall clock)
2 Execution timed out 76 ms 59520 KB Time limit exceeded (wall clock)
3 Execution timed out 63 ms 64628 KB Time limit exceeded (wall clock)
4 Execution timed out 32 ms 57416 KB Time limit exceeded (wall clock)
5 Execution timed out 31 ms 59856 KB Time limit exceeded (wall clock)
6 Execution timed out 42 ms 58912 KB Time limit exceeded (wall clock)
7 Execution timed out 47 ms 59928 KB Time limit exceeded (wall clock)
8 Execution timed out 47 ms 66892 KB Time limit exceeded (wall clock)
9 Execution timed out 70 ms 65728 KB Time limit exceeded (wall clock)
10 Execution timed out 70 ms 72788 KB Time limit exceeded (wall clock)
11 Execution timed out 105 ms 65188 KB Time limit exceeded (wall clock)
12 Runtime error 167 ms 131072 KB Execution killed with signal 11
13 Runtime error 164 ms 131072 KB Execution killed with signal 11
14 Runtime error 160 ms 131072 KB Execution killed with signal 11
15 Runtime error 168 ms 131072 KB Execution killed with signal 11
16 Runtime error 175 ms 131072 KB Execution killed with signal 11
17 Runtime error 155 ms 131072 KB Execution killed with signal 11