oj.uz

답안 #657212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657212 2022-11-09T08:17:40 Z rafatoa Regions (IOI09_regions) C++17
100 / 100
 3883 ms 72652 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];
	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++)
		sort(all(ac[i]));
 
	vvi ans(r+1), ans2(r+1);
	for(int r1=1; r1<=r; r1++){
		if(R[r1].size() <= sq) continue;
		ans[r1] = ans2[r1] = vi(r+1, 0);
			
		//for(int r2=1; r2<=r; r2++){
		//	if(r1 == r2) continue;
		//	int ix = 0, sum = ac[r2][ix].S;
		//	for(int i=0; i<R[r1].size(); i++){
		//		while(ix+1 < ac[r2].size() && ac[r2][ix+1].F <= in[R[r1][i]]) sum += ac[r2][++ix].S;
		//		if(ac[r2][ix].F > in[R[r1][i]]) continue;
		//		ans[r1][r2] += sum;
		//	}
		//}
	}
 
	for(int r1=1; r1<=r; r1++){
		if(R[r1].size() <= sq) continue;
		function<void(int, int)> dfs2 = [&](int s, int cnt){
			if(h[s] == r1) cnt++;
			else if(cnt > 0) ans2[r1][h[s]] += cnt;
			
			for(auto u:adj[s])
				dfs2(u, cnt);
		};
		dfs2(1, 0);
	}
 
	while(q--){
		int r1, r2; cin >> r1 >> r2;
		//if(R[r2].size() > sq) cout << ans[r2][r1] << endl;
		if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
		else {
			if(ac[r1].empty()){
				cout << 0 << endl;
				continue;
			}
			int aux = 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;
				aux += sum;
			}
			cout << aux << endl;
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
	// #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
	
    solve();
    return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:67: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]
   67 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:82: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]
   82 |   if(R[r1].size() <= sq) continue;
      |      ~~~~~~~~~~~~~^~~~~
regions.cpp:96: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]
   96 |   if(R[r1].size() > sq) cout << ans2[r1][r2] << endl;
      |      ~~~~~~~~~~~~~^~~~
regions.cpp:103: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]
  103 |    for(int i=0; i<R[r2].size(); i++){
      |                 ~^~~~~~~~~~~~~
regions.cpp:104: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]
  104 |     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 17 ms 464 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 27 ms 592 KB Output is correct
9 Correct 40 ms 1488 KB Output is correct
10 Correct 94 ms 1744 KB Output is correct
11 Correct 105 ms 2504 KB Output is correct
12 Correct 130 ms 3692 KB Output is correct
13 Correct 163 ms 3744 KB Output is correct
14 Correct 182 ms 4916 KB Output is correct
15 Correct 154 ms 9940 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1356 ms 11416 KB Output is correct
2 Correct 1506 ms 10308 KB Output is correct
3 Correct 1947 ms 15216 KB Output is correct
4 Correct 166 ms 4996 KB Output is correct
5 Correct 358 ms 8132 KB Output is correct
6 Correct 626 ms 14584 KB Output is correct
7 Correct 607 ms 18780 KB Output is correct
8 Correct 1105 ms 36220 KB Output is correct
9 Correct 1743 ms 24884 KB Output is correct
10 Correct 2354 ms 72652 KB Output is correct
11 Correct 2324 ms 28248 KB Output is correct
12 Correct 2043 ms 27448 KB Output is correct
13 Correct 2198 ms 28356 KB Output is correct
14 Correct 3011 ms 35344 KB Output is correct
15 Correct 3883 ms 36120 KB Output is correct
16 Correct 3429 ms 46196 KB Output is correct
17 Correct 3558 ms 51308 KB Output is correct