oj.uz

Submission #657133

# Submission time Handle Problem Language Result Execution time Memory
657133 2022-11-08T22:36:08 Z rafatoa Regions (IOI09_regions) C++17
80 / 100
 8000 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];
	}

	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)/2;

	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);
	
	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 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 7 ms 336 KB Output is correct
6 Correct 15 ms 464 KB Output is correct
7 Correct 19 ms 464 KB Output is correct
8 Correct 35 ms 592 KB Output is correct
9 Correct 38 ms 1488 KB Output is correct
10 Correct 86 ms 1744 KB Output is correct
11 Correct 131 ms 2700 KB Output is correct
12 Correct 107 ms 3708 KB Output is correct
13 Correct 136 ms 4012 KB Output is correct
14 Correct 321 ms 5324 KB Output is correct
15 Correct 401 ms 10652 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 11744 KB Output is correct
2 Correct 1213 ms 10556 KB Output is correct
3 Correct 1662 ms 16084 KB Output is correct
4 Correct 427 ms 11400 KB Output is correct
5 Correct 479 ms 12668 KB Output is correct
6 Correct 961 ms 14584 KB Output is correct
7 Correct 1527 ms 24336 KB Output is correct
8 Correct 3944 ms 36796 KB Output is correct
9 Correct 3423 ms 48412 KB Output is correct
10 Execution timed out 8041 ms 107128 KB Time limit exceeded
11 Runtime error 137 ms 131072 KB Execution killed with signal 9
12 Correct 1525 ms 27544 KB Output is correct
13 Correct 3208 ms 38860 KB Output is correct
14 Correct 3405 ms 35336 KB Output is correct
15 Correct 7849 ms 36940 KB Output is correct
16 Runtime error 116 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8071 ms 52148 KB Time limit exceeded