oj.uz

답안 #655609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655609 2022-11-05T00:46:03 Z rafatoa Regions (IOI09_regions) C++17
1 / 100
 8000 ms 64532 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);
	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)
				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 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(r2 > sq) cout << ans[{r1, r2}] << endl;
		else if(r1 > sq) cout << ans2[{r1, r2}] << endl;
		else {
			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);

	// #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
	
    solve();
    return 0;
}

Compilation message

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

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 3 ms 320 KB Output isn't correct
4 Incorrect 4 ms 336 KB Output isn't correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 16 ms 536 KB Output isn't correct
7 Incorrect 22 ms 680 KB Output isn't correct
8 Incorrect 27 ms 596 KB Output isn't correct
9 Incorrect 34 ms 1696 KB Output isn't correct
10 Incorrect 68 ms 1632 KB Output isn't correct
11 Incorrect 98 ms 2124 KB Output isn't correct
12 Incorrect 125 ms 3428 KB Output isn't correct
13 Incorrect 164 ms 2756 KB Output isn't correct
14 Incorrect 472 ms 3312 KB Output isn't correct
15 Incorrect 698 ms 9404 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8009 ms 9360 KB Time limit exceeded
2 Execution timed out 8047 ms 7116 KB Time limit exceeded
3 Execution timed out 8042 ms 13000 KB Time limit exceeded
4 Incorrect 224 ms 4680 KB Output isn't correct
5 Incorrect 333 ms 9220 KB Output isn't correct
6 Execution timed out 8064 ms 22768 KB Time limit exceeded
7 Execution timed out 8042 ms 64532 KB Time limit exceeded
8 Execution timed out 8032 ms 41348 KB Time limit exceeded
9 Incorrect 905 ms 24796 KB Output isn't correct
10 Execution timed out 8096 ms 53476 KB Time limit exceeded
11 Incorrect 1646 ms 29024 KB Output isn't correct
12 Incorrect 4035 ms 25288 KB Output isn't correct
13 Execution timed out 8022 ms 23852 KB Time limit exceeded
14 Execution timed out 8070 ms 29072 KB Time limit exceeded
15 Execution timed out 8019 ms 28724 KB Time limit exceeded
16 Execution timed out 8058 ms 36264 KB Time limit exceeded
17 Execution timed out 8045 ms 42964 KB Time limit exceeded