oj.uz

답안 #657042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657042 2022-11-08T19:19:57 Z rafatoa Regions (IOI09_regions) C++17
55 / 100
 8000 ms 60732 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];
		});

	vector<vpi> ac(r+1);
	for(int i=1; i<=r; i++){
		for(int j=0; j<R[i].size(); j++){
			ac[i].pb({in[R[i][j]], 1});
			ac[i].pb({in[R[i][j]]+sub[R[i][j]], -1});
		}
		sort(all(ac[i]));

		// //
		// cout << "Region: " << i << "\n";
		// for(int j=0; j<ac[i].size(); j++)
		// 	cout << ac[i][j].F << " " << ac[i][j].S << "\n"; //DEBUGGING
		// cout << "--------------\n";
	}
 
	int sq = sqrt(n);
	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(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
		else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
		else {
			if(ac[r1].empty()){
				cout << 0 << endl;
				continue;
			}
			int ans = 0, ix = 0, sum = ac[r1][ix].S;
			for(int i=0; i<R[r2].size(); i++){
				while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
				if(ac[r1][ix].F > in[R[r2][i]]) continue;
				ans += sum;
			}
			cout << ans << endl;
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:66:17: 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]
   66 |   for(int j=0; j<R[i].size(); j++){
      |                ~^~~~~~~~~~~~
regions.cpp: In lambda function:
regions.cpp:83: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]
   83 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:97: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]
   97 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:110:19: 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]
  110 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:111:24: 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]
  111 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:118: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]
  118 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:119:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~

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 4 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 14 ms 464 KB Output is correct
7 Correct 20 ms 464 KB Output is correct
8 Correct 25 ms 592 KB Output is correct
9 Correct 39 ms 1616 KB Output is correct
10 Correct 76 ms 1668 KB Output is correct
11 Correct 99 ms 2340 KB Output is correct
12 Correct 107 ms 3660 KB Output is correct
13 Correct 130 ms 3436 KB Output is correct
14 Correct 175 ms 4688 KB Output is correct
15 Correct 160 ms 10944 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1540 ms 12024 KB Output is correct
2 Correct 1832 ms 10088 KB Output is correct
3 Correct 2696 ms 16200 KB Output is correct
4 Correct 271 ms 4852 KB Output is correct
5 Correct 294 ms 8732 KB Output is correct
6 Execution timed out 8068 ms 24412 KB Time limit exceeded
7 Execution timed out 8101 ms 51472 KB Time limit exceeded
8 Execution timed out 8099 ms 44464 KB Time limit exceeded
9 Correct 1569 ms 24460 KB Output is correct
10 Execution timed out 8083 ms 60732 KB Time limit exceeded
11 Correct 2617 ms 25668 KB Output is correct
12 Correct 4974 ms 29080 KB Output is correct
13 Execution timed out 8085 ms 28836 KB Time limit exceeded
14 Execution timed out 8092 ms 37384 KB Time limit exceeded
15 Execution timed out 8096 ms 36608 KB Time limit exceeded
16 Execution timed out 8096 ms 43652 KB Time limit exceeded
17 Execution timed out 8096 ms 51556 KB Time limit exceeded