oj.uz

답안 #655596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655596 2022-11-04T21:38:22 Z rafatoa Regions (IOI09_regions) C++17
30 / 100
 2946 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;
	unordered_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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 3 ms 368 KB Output is correct
5 Correct 8 ms 464 KB Output is correct
6 Correct 32 ms 3688 KB Output is correct
7 Correct 29 ms 1420 KB Output is correct
8 Correct 50 ms 2472 KB Output is correct
9 Correct 172 ms 6884 KB Output is correct
10 Correct 172 ms 8896 KB Output is correct
11 Correct 313 ms 5852 KB Output is correct
12 Correct 911 ms 14948 KB Output is correct
13 Correct 212 ms 6856 KB Output is correct
14 Correct 390 ms 4876 KB Output is correct
15 Correct 798 ms 11456 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1772 ms 9460 KB Output is correct
2 Correct 1767 ms 9032 KB Output is correct
3 Correct 2946 ms 14620 KB Output is correct
4 Runtime error 1139 ms 131072 KB Execution killed with signal 9
5 Runtime error 1047 ms 131072 KB Execution killed with signal 9
6 Runtime error 803 ms 131072 KB Execution killed with signal 9
7 Runtime error 573 ms 131072 KB Execution killed with signal 9
8 Runtime error 997 ms 131072 KB Execution killed with signal 9
9 Runtime error 704 ms 131072 KB Execution killed with signal 9
10 Runtime error 1034 ms 131072 KB Execution killed with signal 9
11 Runtime error 1018 ms 131072 KB Execution killed with signal 9
12 Runtime error 1044 ms 131072 KB Execution killed with signal 9
13 Runtime error 888 ms 131072 KB Execution killed with signal 9
14 Runtime error 933 ms 131072 KB Execution killed with signal 9
15 Runtime error 685 ms 131072 KB Execution killed with signal 9
16 Runtime error 749 ms 131072 KB Execution killed with signal 9
17 Runtime error 739 ms 131072 KB Execution killed with signal 9