oj.uz

답안 #657017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657017 2022-11-08T18:18:42 Z rafatoa Regions (IOI09_regions) C++17
30 / 100
 6863 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), R(r+1);
	vi h(n+1);

	cin >> h[1];
	R[h[1]].pb(1);
	for(int i=2; i<=n; i++){
		int p; cin >> p;
		adj[p].pb(i);
		cin >> h[i];
		R[h[i]].pb(i);
	}
 
	vi in(n+1), sub(n+1);
	int time = 0;
	function<void(int)> dfs = [&](int s){
		in[s] = time++;
		sub[s] = 1;
		for(auto u:adj[s]){
			dfs(u);
			sub[s] += sub[u];
		}
	};
	dfs(1);
 
	for(int i=1; i<=r; i++)
		sort(all(R[i]), [&](int a, int b){
			return in[a] < in[b];
		});
 
	int sq = 0;
	map<int, int> mp;
	map<pi, int> ans, ans2;
	function<void(int)> dfs2 = [&](int s){
		if(R[h[s]].size() > sq)
			for(auto &[el, ti]:mp)
				if(el != h[s]) ans[{el, h[s]}] += ti;
		
		mp[h[s]]++;
		for(auto u:adj[s])
			dfs2(u);
		
		mp[h[s]]--;
		if(mp[h[s]] == 0) mp.erase(h[s]);
	};
	dfs2(1);
 
	for(int i=1; i<=r; i++){
		if(R[i].size() <= sq) continue;
		function<void(int, int)> dfs3 = [&](int s, int cnt){
			if(h[s] == i) cnt++;
			else if(cnt > 0) ans2[{i, h[s]}] += cnt;
			
			for(auto u:adj[s])
				dfs3(u, cnt);
		};
		dfs3(1, 0);
	}
 
	while(q--){
		int r1, r2; cin >> r1 >> r2;
		if(r2 > sq) cout << ans[{r1, r2}] << endl;
		else if(r1 > sq) cout << ans2[{r1, r2}] << endl;
		else {
			int sum = 0;
			for(int i=0; i<R[r1].size(); i++)
			for(int j=0; j<R[r2].size(); j++)
				if(in[R[r1][i]] <= in[R[r2][j]] && in[R[r2][j]] < in[R[r1][i]]+sub[R[r1][i]]) sum++;
			cout << sum << endl;
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In lambda function:
regions.cpp:68:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   68 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:82:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   82 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:99:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for(int i=0; i<R[r1].size(); i++)
      |                 ~^~~~~~~~~~~~~
regions.cpp:100:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for(int j=0; j<R[r2].size(); j++)
      |                 ~^~~~~~~~~~~~~

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 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 10 ms 592 KB Output is correct
6 Correct 66 ms 6920 KB Output is correct
7 Correct 31 ms 2384 KB Output is correct
8 Correct 79 ms 4500 KB Output is correct
9 Correct 492 ms 12588 KB Output is correct
10 Correct 437 ms 16896 KB Output is correct
11 Correct 846 ms 10712 KB Output is correct
12 Correct 3219 ms 28124 KB Output is correct
13 Correct 425 ms 11876 KB Output is correct
14 Correct 1047 ms 7976 KB Output is correct
15 Correct 2547 ms 16304 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3653 ms 13848 KB Output is correct
2 Correct 4283 ms 12976 KB Output is correct
3 Correct 6863 ms 21020 KB Output is correct
4 Runtime error 4542 ms 131072 KB Execution killed with signal 9
5 Runtime error 4909 ms 131072 KB Execution killed with signal 9
6 Runtime error 2989 ms 131072 KB Execution killed with signal 9
7 Runtime error 1930 ms 131072 KB Execution killed with signal 9
8 Runtime error 3445 ms 131072 KB Execution killed with signal 9
9 Runtime error 2847 ms 131072 KB Execution killed with signal 9
10 Runtime error 4019 ms 131072 KB Execution killed with signal 9
11 Runtime error 4138 ms 131072 KB Execution killed with signal 9
12 Runtime error 4183 ms 131072 KB Execution killed with signal 9
13 Runtime error 3133 ms 131072 KB Execution killed with signal 9
14 Runtime error 3528 ms 131072 KB Execution killed with signal 9
15 Runtime error 2235 ms 131072 KB Execution killed with signal 9
16 Runtime error 2169 ms 131072 KB Execution killed with signal 9
17 Runtime error 2285 ms 131072 KB Execution killed with signal 9