oj.uz

Submission #655595

# Submission time Handle Problem Language Result Execution time Memory
655595 2022-11-04T21:31:38 Z rafatoa Regions (IOI09_regions) C++17
30 / 100
 3090 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#pragma GCC optimize ("Ofast")

#define double ld

#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define rs resize
#define as assign
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MP make_pair

#define int long long
const int inf = 2e9;
const int INF = 4e18;

void solve(){
	int n, r, q; cin >> n >> r >> q;
	vvi adj(n+1);
	vi h(n+1);

	cin >> h[1];
	for(int i=2; i<=n; i++){
		int x; cin >> x; cin >> h[i];
		adj[x].pb(i); adj[i].pb(x);
	}

	map<pi, int> ans;
	map<int, int> mp;

	function<void(int, int)> dfs = [&](int s, int e){
		for(auto &[el, times]:mp)
			ans[{h[s], el}] += times;
		
		mp[h[s]]++;
		for(auto u:adj[s])
			if(u != e) dfs(u, s);
		
		mp[h[s]]--;
		if(mp[h[s]] == 0) mp.erase(h[s]);
	};
	dfs(1, 0);

	while(q--){
		int r1, r2; cin >> r1 >> r2;
		cout << ans[{r2, r1}] << endl;
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	// #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
	
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 9 ms 464 KB Output is correct
6 Correct 31 ms 3708 KB Output is correct
7 Correct 43 ms 1512 KB Output is correct
8 Correct 52 ms 2724 KB Output is correct
9 Correct 151 ms 6964 KB Output is correct
10 Correct 199 ms 8828 KB Output is correct
11 Correct 324 ms 6036 KB Output is correct
12 Correct 866 ms 14896 KB Output is correct
13 Correct 251 ms 7012 KB Output is correct
14 Correct 443 ms 4804 KB Output is correct
15 Correct 941 ms 12048 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 9672 KB Output is correct
2 Correct 1828 ms 9128 KB Output is correct
3 Correct 3090 ms 15168 KB Output is correct
4 Runtime error 1082 ms 131072 KB Execution killed with signal 9
5 Runtime error 997 ms 131072 KB Execution killed with signal 9
6 Runtime error 774 ms 131072 KB Execution killed with signal 9
7 Runtime error 545 ms 131072 KB Execution killed with signal 9
8 Runtime error 928 ms 131072 KB Execution killed with signal 9
9 Runtime error 614 ms 131072 KB Execution killed with signal 9
10 Runtime error 983 ms 131072 KB Execution killed with signal 9
11 Runtime error 984 ms 131072 KB Execution killed with signal 9
12 Runtime error 942 ms 131072 KB Execution killed with signal 9
13 Runtime error 774 ms 131072 KB Execution killed with signal 9
14 Runtime error 879 ms 131072 KB Execution killed with signal 9
15 Runtime error 694 ms 131072 KB Execution killed with signal 9
16 Runtime error 720 ms 131072 KB Execution killed with signal 9
17 Runtime error 702 ms 131072 KB Execution killed with signal 9