oj.uz

Submission #924985

# Submission time Handle Problem Language Result Execution time Memory
924985 2024-02-10T09:40:52 Z josanneo22 Regions (IOI09_regions) C++17
13 / 100
 8000 ms 44984 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int _ = 2E5 + 500;
int r[_], N, R, Q, vis[_], val[504][504], cal[504][504];
vector<int> child[_], officer[_];
void dfs(int u){
	vis[u]++;
	for(auto & v : child[u]) 
		dfs(v);
}
i64 work(int x, int y){
	i64 ans = 0;
	for(auto person : officer[x])
		dfs(person);
	for(int i = 1; i <= N; i++){
		if(r[i] == y)
			ans += (vis[i]);
		vis[i] = 0;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> N >> R >> Q;
	cin >> r[1];
	officer[r[1]].push_back(1);
	for(int i = 2; i <= N; i++){
		int p; cin >> p >> r[i];
		child[p].push_back(i);
		officer[r[i]].push_back(i);
	}
	while(Q--){
		int r1, r2; cin >> r1 >> r2;
		i64 ans;
		if(cal[r1][r2] == false){
			ans = work(r1, r2);
			val[r1][r2] = ans;
			cal[r1][r2] = true;
		}
		else ans = val[r1][r2];
		cout << ans << endl;
	}
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 5 ms 12888 KB Output is correct
5 Correct 8 ms 12888 KB Output is correct
6 Correct 24 ms 12888 KB Output is correct
7 Correct 31 ms 12888 KB Output is correct
8 Correct 60 ms 12888 KB Output is correct
9 Correct 1030 ms 13144 KB Output is correct
10 Correct 400 ms 13140 KB Output is correct
11 Correct 2547 ms 13596 KB Output is correct
12 Execution timed out 8032 ms 13788 KB Time limit exceeded
13 Correct 781 ms 13400 KB Output is correct
14 Correct 6352 ms 13912 KB Output is correct
15 Execution timed out 8079 ms 15156 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8007 ms 15804 KB Time limit exceeded
2 Execution timed out 8019 ms 14984 KB Time limit exceeded
3 Execution timed out 8096 ms 16824 KB Time limit exceeded
4 Runtime error 21 ms 27992 KB Execution killed with signal 11
5 Runtime error 20 ms 28668 KB Execution killed with signal 11
6 Runtime error 22 ms 29220 KB Execution killed with signal 11
7 Runtime error 26 ms 30616 KB Execution killed with signal 11
8 Runtime error 32 ms 33960 KB Execution killed with signal 11
9 Runtime error 51 ms 37792 KB Execution killed with signal 11
10 Runtime error 107 ms 43304 KB Execution killed with signal 11
11 Runtime error 77 ms 37316 KB Execution killed with signal 11
12 Runtime error 55 ms 41040 KB Execution killed with signal 11
13 Runtime error 56 ms 39924 KB Execution killed with signal 11
14 Runtime error 62 ms 40288 KB Execution killed with signal 11
15 Runtime error 153 ms 44984 KB Execution killed with signal 11
16 Runtime error 60 ms 42400 KB Execution killed with signal 11
17 Runtime error 62 ms 42340 KB Execution killed with signal 11