oj.uz

Submission #733234

# Submission time Handle Problem Language Result Execution time Memory
733234 2023-04-30T09:34:22 Z penguin133 Regions (IOI09_regions) C++17
30 / 100
 2632 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, r, q;
map <int, int> mp[200005];
vector <int> adj[200005];
int A[200005];
map <int, int> fin[25005];
 
void dfs(int x, int par){
	mp[x][A[x]]++;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
		if(mp[i].size() > mp[x].size())swap(mp[x], mp[i]);
		for(auto [j, k] : mp[i])mp[x][j] += k;
	}
	for(auto [i, j] : mp[x])fin[A[x]][i] += j;
}
 
void solve(){
	cin >> n >> r >> q;
	cin >> A[1];
	for(int i=2;i<=n;i++){
		int x; cin >> x >> A[i];
		adj[x].push_back(i);
	}
	dfs(1, -1);
	while(q--){
		int x, y; cin >> x >> y;
		cout << fin[x][y] << endl;
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

regions.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15512 KB Output is correct
2 Correct 10 ms 15568 KB Output is correct
3 Correct 11 ms 15604 KB Output is correct
4 Correct 14 ms 15760 KB Output is correct
5 Correct 20 ms 15640 KB Output is correct
6 Correct 32 ms 18192 KB Output is correct
7 Correct 44 ms 16556 KB Output is correct
8 Correct 57 ms 17376 KB Output is correct
9 Correct 152 ms 20844 KB Output is correct
10 Correct 156 ms 23188 KB Output is correct
11 Correct 197 ms 21208 KB Output is correct
12 Correct 544 ms 27628 KB Output is correct
13 Correct 182 ms 23068 KB Output is correct
14 Correct 216 ms 22072 KB Output is correct
15 Correct 828 ms 26576 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 26732 KB Output is correct
2 Correct 964 ms 27944 KB Output is correct
3 Correct 2632 ms 31196 KB Output is correct
4 Runtime error 644 ms 131072 KB Execution killed with signal 9
5 Runtime error 1052 ms 131072 KB Execution killed with signal 9
6 Runtime error 736 ms 131072 KB Execution killed with signal 9
7 Runtime error 462 ms 131072 KB Execution killed with signal 9
8 Runtime error 832 ms 131072 KB Execution killed with signal 9
9 Runtime error 582 ms 131072 KB Execution killed with signal 9
10 Runtime error 862 ms 131072 KB Execution killed with signal 9
11 Runtime error 685 ms 131072 KB Execution killed with signal 9
12 Runtime error 860 ms 131072 KB Execution killed with signal 9
13 Runtime error 703 ms 131072 KB Execution killed with signal 9
14 Runtime error 790 ms 131072 KB Execution killed with signal 9
15 Runtime error 625 ms 131072 KB Execution killed with signal 9
16 Runtime error 602 ms 131072 KB Execution killed with signal 9
17 Runtime error 710 ms 131072 KB Execution killed with signal 9