oj.uz

Submission #657018

# Submission time Handle Problem Language Result Execution time Memory
657018 2022-11-08T18:19:32 Z rafatoa Regions (IOI09_regions) C++17
15 / 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];
		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 = 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;
		
		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;
			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 << endl;
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
    solve();
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 11 ms 592 KB Output is correct
6 Correct 63 ms 6856 KB Output is correct
7 Correct 45 ms 2228 KB Output is correct
8 Correct 89 ms 4436 KB Output is correct
9 Correct 497 ms 12564 KB Output is correct
10 Correct 485 ms 16756 KB Output is correct
11 Correct 959 ms 10800 KB Output is correct
12 Correct 3767 ms 28020 KB Output is correct
13 Correct 629 ms 11632 KB Output is correct
14 Correct 1600 ms 8040 KB Output is correct
15 Correct 3702 ms 16164 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8076 ms 13668 KB Time limit exceeded
2 Execution timed out 8041 ms 12948 KB Time limit exceeded
3 Execution timed out 8080 ms 21008 KB Time limit exceeded
4 Runtime error 4747 ms 131072 KB Execution killed with signal 9
5 Runtime error 4669 ms 131072 KB Execution killed with signal 9
6 Runtime error 3102 ms 131072 KB Execution killed with signal 9
7 Runtime error 1988 ms 131072 KB Execution killed with signal 9
8 Runtime error 3557 ms 131072 KB Execution killed with signal 9
9 Runtime error 2675 ms 131072 KB Execution killed with signal 9
10 Runtime error 3725 ms 131072 KB Execution killed with signal 9
11 Runtime error 3933 ms 131072 KB Execution killed with signal 9
12 Runtime error 3776 ms 131072 KB Execution killed with signal 9
13 Runtime error 2844 ms 131072 KB Execution killed with signal 9
14 Runtime error 3525 ms 131072 KB Execution killed with signal 9
15 Runtime error 2173 ms 131072 KB Execution killed with signal 9
16 Runtime error 2309 ms 131072 KB Execution killed with signal 9
17 Runtime error 2338 ms 131072 KB Execution killed with signal 9