oj.uz

Submission #657151

# Submission time Handle Problem Language Result Execution time Memory
657151 2022-11-08T23:26:03 Z rafatoa Regions (IOI09_regions) C++17
48 / 100
 2285 ms 92652 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++)
		sort(all(ac[i]));
 
	vvi ans(r+1), ans2(r+1);
	for(int r1=1; r1<=r; r1++){
		if(R[r1].size() <= sq) continue;
		ans[r1] = ans2[r1] = vi(r+1, 0);
			
		for(int r2=1; r2<=r; r2++){
			if(r1 == r2) continue;
			int ix = 0, sum = ac[r2][ix].S;
			for(int i=0; i<R[r1].size(); i++){
				while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S;
				if(ac[r2][ix].F > in[R[r1][i]]) continue;
				ans[r1][r2] += sum;
			}
		}
	}

	for(int r1=1; r1<=r; r1++){
		if(R[r1].size() <= sq) continue;
		function<void(int, int)> dfs2 = [&](int s, int cnt){
			if(h[s] == r1) cnt++;
			else if(cnt > 0) ans2[r1][h[s]] += cnt;
			
			for(auto u:adj[s])
				dfs2(u, cnt);
		};
		dfs2(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 aux = 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;
				aux += sum;
			}
			cout << aux << endl;
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	// #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:68: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]
   68 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:74: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]
   74 |    for(int i=0; i<R[r1].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:75: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]
   75 |     while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~
regions.cpp:83: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]
   83 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:96: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]
   96 |   if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:97: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]
   97 |   else if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:104: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]
  104 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:105: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]
  105 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 11
2 Runtime error 1 ms 336 KB Execution killed with signal 11
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 26 ms 464 KB Output is correct
8 Correct 34 ms 592 KB Output is correct
9 Correct 46 ms 1488 KB Output is correct
10 Correct 41 ms 1744 KB Output is correct
11 Correct 100 ms 2480 KB Output is correct
12 Correct 143 ms 3696 KB Output is correct
13 Correct 100 ms 3744 KB Output is correct
14 Correct 180 ms 4932 KB Output is correct
15 Correct 176 ms 9912 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 11440 KB Output is correct
2 Correct 973 ms 10336 KB Output is correct
3 Correct 1432 ms 15184 KB Output is correct
4 Correct 230 ms 5012 KB Output is correct
5 Correct 315 ms 8116 KB Output is correct
6 Runtime error 29 ms 16052 KB Execution killed with signal 11
7 Runtime error 44 ms 22280 KB Execution killed with signal 11
8 Runtime error 76 ms 41732 KB Execution killed with signal 11
9 Correct 1163 ms 24920 KB Output is correct
10 Runtime error 103 ms 68364 KB Execution killed with signal 11
11 Correct 2285 ms 28208 KB Output is correct
12 Runtime error 145 ms 54880 KB Execution killed with signal 11
13 Runtime error 115 ms 56892 KB Execution killed with signal 11
14 Runtime error 133 ms 58140 KB Execution killed with signal 11
15 Runtime error 770 ms 72216 KB Execution killed with signal 11
16 Runtime error 146 ms 92652 KB Execution killed with signal 11
17 Runtime error 137 ms 89776 KB Execution killed with signal 11