oj.uz

Submission #657205

# Submission time Handle Problem Language Result Execution time Memory
657205 2022-11-09T07:18:31 Z rafatoa Regions (IOI09_regions) C++17
49 / 100
 2050 ms 92584 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];
	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:67: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]
   67 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:73: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]
   73 |    for(int i=0; i<R[r1].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:74: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]
   74 |     while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~
regions.cpp:82: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]
   82 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:95: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]
   95 |   if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:96: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]
   96 |   else if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:103: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]
  103 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:104: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]
  104 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 11
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 17 ms 464 KB Output is correct
7 Correct 34 ms 464 KB Output is correct
8 Correct 39 ms 592 KB Output is correct
9 Correct 41 ms 1488 KB Output is correct
10 Correct 77 ms 1744 KB Output is correct
11 Correct 114 ms 2492 KB Output is correct
12 Correct 111 ms 3688 KB Output is correct
13 Correct 123 ms 3740 KB Output is correct
14 Correct 179 ms 4816 KB Output is correct
15 Correct 127 ms 9936 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 11420 KB Output is correct
2 Correct 1078 ms 10312 KB Output is correct
3 Correct 1566 ms 15212 KB Output is correct
4 Correct 228 ms 4996 KB Output is correct
5 Correct 316 ms 8120 KB Output is correct
6 Runtime error 35 ms 16072 KB Execution killed with signal 11
7 Runtime error 41 ms 22296 KB Execution killed with signal 11
8 Runtime error 71 ms 41784 KB Execution killed with signal 11
9 Correct 1545 ms 24880 KB Output is correct
10 Runtime error 114 ms 68284 KB Execution killed with signal 11
11 Correct 2050 ms 28252 KB Output is correct
12 Runtime error 138 ms 54840 KB Execution killed with signal 11
13 Runtime error 112 ms 56796 KB Execution killed with signal 11
14 Runtime error 133 ms 58100 KB Execution killed with signal 11
15 Runtime error 835 ms 72276 KB Execution killed with signal 11
16 Runtime error 132 ms 92584 KB Execution killed with signal 11
17 Runtime error 131 ms 89764 KB Execution killed with signal 11