oj.uz

답안 #657113

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

	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++){
		if(R[i].size() > sq) continue;
		sort(all(ac[i]));
	}

	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:65: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]
   65 |   if(R[i].size() > sq) continue;
      |      ~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:72: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]
   72 |   if(R[h[s]].size() > sq)
      |      ~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'void solve()':
regions.cpp:86: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]
   86 |   if(R[i].size() <= sq) continue;
      |      ~~~~~~~~~~~~^~~~~
regions.cpp:99: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]
   99 |   if(R[r2].size() > sq) cout << ans[{r1, r2}] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:100: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]
  100 |   else if(R[r1].size() > sq) cout << ans2[{r1, r2}] << endl;
      |           ~~~~~~~~~~~~~^~~~
regions.cpp:107: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]
  107 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:108: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]
  108 |     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 1 ms 208 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 20 ms 464 KB Output is correct
7 Correct 32 ms 464 KB Output is correct
8 Correct 24 ms 592 KB Output is correct
9 Correct 26 ms 1616 KB Output is correct
10 Correct 93 ms 1744 KB Output is correct
11 Correct 112 ms 2484 KB Output is correct
12 Correct 85 ms 3812 KB Output is correct
13 Correct 148 ms 3736 KB Output is correct
14 Correct 190 ms 4960 KB Output is correct
15 Correct 247 ms 11164 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1294 ms 12052 KB Output is correct
2 Correct 1740 ms 10400 KB Output is correct
3 Correct 2468 ms 16268 KB Output is correct
4 Correct 291 ms 5020 KB Output is correct
5 Correct 191 ms 8752 KB Output is correct
6 Execution timed out 8074 ms 23916 KB Time limit exceeded
7 Execution timed out 8042 ms 32460 KB Time limit exceeded
8 Execution timed out 8067 ms 42032 KB Time limit exceeded
9 Correct 1595 ms 25052 KB Output is correct
10 Execution timed out 8035 ms 61528 KB Time limit exceeded
11 Correct 2952 ms 27368 KB Output is correct
12 Execution timed out 8026 ms 27740 KB Time limit exceeded
13 Execution timed out 8071 ms 29196 KB Time limit exceeded
14 Execution timed out 8026 ms 36892 KB Time limit exceeded
15 Execution timed out 8064 ms 37012 KB Time limit exceeded
16 Execution timed out 8076 ms 47032 KB Time limit exceeded
17 Execution timed out 8066 ms 53604 KB Time limit exceeded