oj.uz

답안 #657044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657044 2022-11-08T19:23:37 Z rafatoa Regions (IOI09_regions) C++17
55 / 100
 8000 ms 58656 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);

	vector<vpi> ac(r+1);
	for(int i=1; i<=r; i++){
		if(R[i].size() > sq) continue;
		for(int j=0; j<R[i].size(); j++){
			ac[i].pb({in[R[i][j]], 1});
			ac[i].pb({in[R[i][j]]+sub[R[i][j]], -1});
		}
		sort(all(ac[i]));

		// //
		// cout << "Region: " << i << "\n";
		// for(int j=0; j<ac[i].size(); j++)
		// 	cout << ac[i][j].F << " " << ac[i][j].S << "\n"; //DEBUGGING
		// cout << "--------------\n";
	}

	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;
		if(R[r2].size() > sq) cout << ans[{r1, r2}] << 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:68: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]
   68 |   if(R[i].size() > sq) continue;
      |      ~~~~~~~~~~~~^~~~
regions.cpp:69:17: 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]
   69 |   for(int j=0; j<R[i].size(); j++){
      |                ~^~~~~~~~~~~~
regions.cpp: In lambda function:
regions.cpp:85: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]
   85 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:99: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]
   99 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:112: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]
  112 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:113: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]
  113 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:120: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]
  120 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:121: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]
  121 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 12 ms 464 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 22 ms 592 KB Output is correct
9 Correct 32 ms 1616 KB Output is correct
10 Correct 80 ms 1668 KB Output is correct
11 Correct 97 ms 2312 KB Output is correct
12 Correct 128 ms 3536 KB Output is correct
13 Correct 163 ms 3408 KB Output is correct
14 Correct 190 ms 4624 KB Output is correct
15 Correct 232 ms 10948 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1466 ms 10700 KB Output is correct
2 Correct 1383 ms 8820 KB Output is correct
3 Correct 2462 ms 14920 KB Output is correct
4 Correct 175 ms 4832 KB Output is correct
5 Correct 350 ms 8724 KB Output is correct
6 Execution timed out 8058 ms 23568 KB Time limit exceeded
7 Execution timed out 8093 ms 33436 KB Time limit exceeded
8 Execution timed out 8092 ms 42476 KB Time limit exceeded
9 Correct 1360 ms 24560 KB Output is correct
10 Execution timed out 8079 ms 58656 KB Time limit exceeded
11 Correct 2833 ms 25668 KB Output is correct
12 Correct 4315 ms 28180 KB Output is correct
13 Execution timed out 8099 ms 28928 KB Time limit exceeded
14 Execution timed out 8089 ms 35420 KB Time limit exceeded
15 Execution timed out 8080 ms 35860 KB Time limit exceeded
16 Execution timed out 8084 ms 42980 KB Time limit exceeded
17 Execution timed out 8099 ms 49428 KB Time limit exceeded