oj.uz

Submission #657130

# Submission time Handle Problem Language Result Execution time Memory
657130 2022-11-08T22:33:57 Z rafatoa Regions (IOI09_regions) C++17
100 / 100
 7671 ms 73120 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];
	}

	vector<vpi> ac(r+1);
	vi in(n+1), sub(n+1);
	int time = 0;
	function<void(int)> dfs = [&](int s){
		R[h[s]].pb(s);
		in[s] = time++;
		sub[s] = 1;
		for(auto u:adj[s]){
			dfs(u);
			sub[s] += sub[u];
		}
		ac[h[s]].pb({in[s], 1});
		ac[h[s]].pb({in[s]+sub[s], -1});
	};
	dfs(1);

	int sq = 2*sqrt(n)/3;

	for(int i=1; i<=r; i++){
		if(R[i].size() > sq) continue;
		sort(all(ac[i]));
	}

	vvi ans(r+1), ans2(r+1);
	for(int i=1; i<=r; i++)
		if(R[i].size() > sq) ans[i] = ans2[i] = vi(r+1, 0);
	
	unordered_map<int, int> mp;
	function<void(int)> dfs2 = [&](int s){
		if(R[h[s]].size() > sq)
			for(auto &[el, ti]:mp)
				if(el != h[s]) ans[h[s]][el] += 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[r2][r1] << 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:65: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]
   65 |   if(R[i].size() > sq) continue;
      |      ~~~~~~~~~~~~^~~~
regions.cpp:71: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]
   71 |   if(R[i].size() > sq) ans[i] = ans2[i] = vi(r+1, 0);
      |      ~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:75: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]
   75 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:89: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]
   89 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:102: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]
  102 |   if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:103: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]
  103 |   else if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:110: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]
  110 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:111: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]
  111 |     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

# 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 4 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 16 ms 464 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 27 ms 592 KB Output is correct
9 Correct 50 ms 1488 KB Output is correct
10 Correct 101 ms 1728 KB Output is correct
11 Correct 82 ms 2488 KB Output is correct
12 Correct 134 ms 3708 KB Output is correct
13 Correct 147 ms 3748 KB Output is correct
14 Correct 332 ms 5452 KB Output is correct
15 Correct 396 ms 10652 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 11620 KB Output is correct
2 Correct 1152 ms 10564 KB Output is correct
3 Correct 1443 ms 15180 KB Output is correct
4 Correct 279 ms 11340 KB Output is correct
5 Correct 348 ms 8196 KB Output is correct
6 Correct 841 ms 14540 KB Output is correct
7 Correct 1100 ms 21348 KB Output is correct
8 Correct 2492 ms 36460 KB Output is correct
9 Correct 3108 ms 48480 KB Output is correct
10 Correct 3945 ms 73120 KB Output is correct
11 Correct 4003 ms 69552 KB Output is correct
12 Correct 1167 ms 27504 KB Output is correct
13 Correct 1967 ms 28404 KB Output is correct
14 Correct 2748 ms 35336 KB Output is correct
15 Correct 4867 ms 36536 KB Output is correct
16 Correct 6599 ms 47136 KB Output is correct
17 Correct 7671 ms 52068 KB Output is correct