oj.uz

답안 #689600

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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