Submission #657044

#	Time	Username	Problem	Language	Result	Execution time	Memory
657044		rafatoa	Regions (IOI09_regions)	C++17	55 / 100	8099 ms	58656 KiB

regions

#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 = sqrt(n);

	vector<vpi> ac(r+1);
	for(int i=1; i<=r; i++){
		if(R[i].size() > sq) continue;
		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";
	}

	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 (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:68: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]
   68 |   if(R[i].size() > sq) continue;
      |      ~~~~~~~~~~~~^~~~
regions.cpp:69: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]
   69 |   for(int j=0; j<R[i].size(); j++){
      |                ~^~~~~~~~~~~~
regions.cpp: In lambda function:
regions.cpp:85: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]
   85 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:99: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]
   99 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:112: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]
  112 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:113: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]
  113 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:120: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]
  120 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:121: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]
  121 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85