oj.uz

Submission #924982

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

const int _ = 2E5 + 500;
int r[_], N, R, Q, vis[_];
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 = work(r1, r2);
		cout << ans << endl;
	}
}

Subtask #1
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 5 ms 10840 KB Output is correct
5 Correct 13 ms 10840 KB Output is correct
6 Correct 29 ms 10840 KB Output is correct
7 Correct 68 ms 10840 KB Output is correct
8 Correct 140 ms 10840 KB Output is correct
9 Correct 1439 ms 11096 KB Output is correct
10 Correct 2162 ms 11096 KB Output is correct
11 Execution timed out 8064 ms 11352 KB Time limit exceeded
12 Execution timed out 8045 ms 11728 KB Time limit exceeded
13 Execution timed out 8042 ms 11352 KB Time limit exceeded
14 Execution timed out 8026 ms 11784 KB Time limit exceeded
15 Execution timed out 8101 ms 13084 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 13800 KB Time limit exceeded
2 Execution timed out 8028 ms 13084 KB Time limit exceeded
3 Execution timed out 8095 ms 14844 KB Time limit exceeded
4 Execution timed out 8069 ms 11864 KB Time limit exceeded
5 Execution timed out 8066 ms 12904 KB Time limit exceeded
6 Execution timed out 8100 ms 12628 KB Time limit exceeded
7 Execution timed out 8077 ms 13348 KB Time limit exceeded
8 Execution timed out 8029 ms 16200 KB Time limit exceeded
9 Execution timed out 8007 ms 16936 KB Time limit exceeded
10 Execution timed out 8098 ms 19812 KB Time limit exceeded
11 Execution timed out 8098 ms 16424 KB Time limit exceeded
12 Execution timed out 8099 ms 18496 KB Time limit exceeded
13 Execution timed out 8050 ms 18224 KB Time limit exceeded
14 Execution timed out 8045 ms 18288 KB Time limit exceeded
15 Execution timed out 8053 ms 20444 KB Time limit exceeded
16 Execution timed out 8010 ms 22588 KB Time limit exceeded
17 Execution timed out 8013 ms 21956 KB Time limit exceeded