oj.uz

답안 #657039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657039 2022-11-08T19:18:25 Z rafatoa Regions (IOI09_regions) C++17
0 / 100
 8000 ms 60276 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];
		});

	vector<vpi> ac(r+1);
	for(int i=1; i<=r; i++){
		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";
	}
 
	int sq = sqrt(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\n";
				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 << "\n";
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:66: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]
   66 |   for(int j=0; j<R[i].size(); j++){
      |                ~^~~~~~~~~~~~
regions.cpp: In lambda function:
regions.cpp:83: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]
   83 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:97: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]
   97 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:110: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]
  110 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:111: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]
  111 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:118: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]
  118 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:119: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]
  119 |     while(ix+1 < ac[r1].size() && ac[r1][ix+1].F <= in[R[r2][i]]) sum += ac[r1][++ix].S;
      |           ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
3 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 340 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 464 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 464 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 592 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 1652 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 1616 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 2364 KB Time limit exceeded (wall clock)
12 Execution timed out 16 ms 3536 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 3408 KB Time limit exceeded (wall clock)
14 Execution timed out 29 ms 4624 KB Time limit exceeded (wall clock)
15 Execution timed out 27 ms 10832 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 737 ms 11984 KB Time limit exceeded (wall clock)
2 Execution timed out 615 ms 10136 KB Time limit exceeded (wall clock)
3 Execution timed out 836 ms 16196 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 4816 KB Time limit exceeded (wall clock)
5 Execution timed out 34 ms 8704 KB Time limit exceeded (wall clock)
6 Execution timed out 8085 ms 24188 KB Time limit exceeded
7 Execution timed out 8039 ms 33816 KB Time limit exceeded
8 Execution timed out 8068 ms 44228 KB Time limit exceeded
9 Execution timed out 138 ms 24452 KB Time limit exceeded (wall clock)
10 Execution timed out 8076 ms 60276 KB Time limit exceeded
11 Execution timed out 160 ms 25548 KB Time limit exceeded (wall clock)
12 Execution timed out 3352 ms 29112 KB Time limit exceeded (wall clock)
13 Execution timed out 8036 ms 28784 KB Time limit exceeded
14 Execution timed out 8042 ms 37128 KB Time limit exceeded
15 Execution timed out 8068 ms 36588 KB Time limit exceeded
16 Execution timed out 8041 ms 43692 KB Time limit exceeded
17 Execution timed out 8102 ms 51512 KB Time limit exceeded