oj.uz

Submission #657110

# Submission time Handle Problem Language Result Execution time Memory
657110 2022-11-08T21:45:18 Z rafatoa Regions (IOI09_regions) C++17
55 / 100
 8000 ms 61932 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 = sqrt(n);

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

	int iterat = 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;
				iterat++;
			}
		
		mp[h[s]]++;
		for(auto u:adj[s])
			dfs2(u);
		
		mp[h[s]]--;
		if(mp[h[s]] == 0) mp.erase(h[s]);
	};
	dfs2(1);

	assert(iterat <= 2*n*sq);
 
	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: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: In lambda function:
regions.cpp:74: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]
   74 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:92: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]
   92 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:105: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]
  105 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:106: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]
  106 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:113: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]
  113 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:114: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]
  114 |     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 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 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 22 ms 464 KB Output is correct
7 Correct 28 ms 464 KB Output is correct
8 Correct 33 ms 592 KB Output is correct
9 Correct 34 ms 1680 KB Output is correct
10 Correct 68 ms 1744 KB Output is correct
11 Correct 80 ms 2488 KB Output is correct
12 Correct 116 ms 3816 KB Output is correct
13 Correct 149 ms 3728 KB Output is correct
14 Correct 178 ms 4952 KB Output is correct
15 Correct 165 ms 11164 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1618 ms 12164 KB Output is correct
2 Correct 1535 ms 10468 KB Output is correct
3 Correct 2318 ms 16324 KB Output is correct
4 Correct 177 ms 4872 KB Output is correct
5 Correct 311 ms 8788 KB Output is correct
6 Execution timed out 8012 ms 24652 KB Time limit exceeded
7 Execution timed out 8018 ms 54840 KB Time limit exceeded
8 Execution timed out 8032 ms 45500 KB Time limit exceeded
9 Correct 1602 ms 24800 KB Output is correct
10 Execution timed out 8035 ms 61932 KB Time limit exceeded
11 Correct 2228 ms 27124 KB Output is correct
12 Correct 4277 ms 29388 KB Output is correct
13 Execution timed out 8101 ms 29112 KB Time limit exceeded
14 Execution timed out 8026 ms 37496 KB Time limit exceeded
15 Execution timed out 8042 ms 37348 KB Time limit exceeded
16 Execution timed out 8031 ms 47108 KB Time limit exceeded
17 Execution timed out 8036 ms 54212 KB Time limit exceeded