oj.uz

Submission #655602

# Submission time Handle Problem Language Result Execution time Memory
655602 2022-11-05T00:10:11 Z rafatoa Regions (IOI09_regions) C++17
0 / 100
 8000 ms 63104 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];
		R[h[i]].pb(i);
	}

	vi in(n+1), sub(n+1);
	int time = 0;
	function<void(int)> dfs = [&](int s){
		in[s] = time++;
		sub[s] = 1;
		for(auto u:adj[s]){
			dfs(u);
			sub[s] += sub[u];
		}
	};
	dfs(1);

	for(int i=1; i<=r; i++)
		sort(all(R[i]), [&](int a, int b){
			return in[a] < in[b];
		});

	int sq = sqrt(n);
	map<int, int> mp;
	map<pi, int> ans;
	function<void(int)> dfs2 = [&](int s){
		if(R[h[s]].size() > sq)
			for(auto &[el, ti]:mp)
				ans[{el, h[s]}] += 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 > 0) ans[{i, h[s]}] += cnt;
			if(h[s] == i) cnt++;
			
			for(auto u:adj[s])
				dfs3(u, cnt);
		};
		dfs3(1, 0);
	}

	while(q--){
		int r1, r2; cin >> r1 >> r2;
		if(r1 > sq || r2 > sq){
			cout << ans[{r1, r2}] << endl;
		} else {
			int sum = 0;
			for(int i=0; i<R[r1].size(); i++)
			for(int j=0; j<R[r2].size(); j++)
				if(in[R[r1][i]] <= in[R[r2][j]] && in[R[r2][j]] < in[R[r1][i]]+sub[R[r1][i]]) sum++;
			cout << sum << "\n";
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In lambda function:
regions.cpp:67: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]
   67 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:81: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]
   81 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:98: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]
   98 |    for(int i=0; i<R[r1].size(); i++)
      |                 ~^~~~~~~~~~~~~
regions.cpp:99: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]
   99 |    for(int j=0; j<R[r2].size(); j++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 324 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 336 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 464 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 464 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 464 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 1360 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 1232 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 1744 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 2640 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 2128 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 3024 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 8912 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 766 ms 9400 KB Time limit exceeded (wall clock)
2 Execution timed out 588 ms 7304 KB Time limit exceeded (wall clock)
3 Execution timed out 797 ms 13056 KB Time limit exceeded (wall clock)
4 Execution timed out 19 ms 3280 KB Time limit exceeded (wall clock)
5 Execution timed out 24 ms 6992 KB Time limit exceeded (wall clock)
6 Execution timed out 8042 ms 22608 KB Time limit exceeded
7 Execution timed out 7638 ms 63104 KB Time limit exceeded (wall clock)
8 Execution timed out 8031 ms 40932 KB Time limit exceeded
9 Execution timed out 114 ms 16724 KB Time limit exceeded (wall clock)
10 Execution timed out 8010 ms 53208 KB Time limit exceeded
11 Execution timed out 223 ms 17716 KB Time limit exceeded (wall clock)
12 Execution timed out 3326 ms 21744 KB Time limit exceeded (wall clock)
13 Execution timed out 7657 ms 22964 KB Time limit exceeded (wall clock)
14 Execution timed out 8013 ms 28832 KB Time limit exceeded
15 Execution timed out 8034 ms 28744 KB Time limit exceeded
16 Execution timed out 8042 ms 36568 KB Time limit exceeded
17 Execution timed out 8026 ms 42808 KB Time limit exceeded