oj.uz

Submission #924983

# Submission time Handle Problem Language Result Execution time Memory
924983 2024-02-10T09:38:02 Z josanneo22 Regions (IOI09_regions) C++17
11 / 100
 8000 ms 48464 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] = 1;
	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(vis[i] && r[i] == y) 
				ans++;
			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
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12884 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 10 ms 12888 KB Output is correct
6 Correct 28 ms 12992 KB Output is correct
7 Correct 53 ms 12888 KB Output is correct
8 Correct 116 ms 12888 KB Output is correct
9 Correct 1306 ms 13144 KB Output is correct
10 Correct 1586 ms 13144 KB Output is correct
11 Correct 7785 ms 13400 KB Output is correct
12 Execution timed out 8093 ms 13656 KB Time limit exceeded
13 Execution timed out 8064 ms 13400 KB Time limit exceeded
14 Execution timed out 8042 ms 13912 KB Time limit exceeded
15 Execution timed out 8029 ms 15160 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 15808 KB Time limit exceeded
2 Execution timed out 8021 ms 14980 KB Time limit exceeded
3 Execution timed out 8031 ms 17040 KB Time limit exceeded
4 Runtime error 23 ms 27852 KB Execution killed with signal 11
5 Runtime error 19 ms 28796 KB Execution killed with signal 11
6 Runtime error 21 ms 29116 KB Execution killed with signal 11
7 Runtime error 28 ms 30568 KB Execution killed with signal 11
8 Runtime error 33 ms 33844 KB Execution killed with signal 11
9 Runtime error 49 ms 37596 KB Execution killed with signal 11
10 Runtime error 63 ms 40456 KB Execution killed with signal 11
11 Runtime error 61 ms 37372 KB Execution killed with signal 11
12 Runtime error 55 ms 40940 KB Execution killed with signal 11
13 Runtime error 57 ms 39920 KB Execution killed with signal 11
14 Runtime error 62 ms 40160 KB Execution killed with signal 11
15 Runtime error 233 ms 44976 KB Execution killed with signal 11
16 Runtime error 71 ms 48464 KB Execution killed with signal 11
17 Runtime error 64 ms 42376 KB Execution killed with signal 11