oj.uz

답안 #655608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655608 2022-11-05T00:29:00 Z rafatoa Regions (IOI09_regions) C++17
1 / 100
 8000 ms 52884 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 208 KB Output isn't correct
4 Incorrect 5 ms 328 KB Output isn't correct
5 Incorrect 7 ms 336 KB Output isn't correct
6 Incorrect 17 ms 580 KB Output isn't correct
7 Incorrect 27 ms 560 KB Output isn't correct
8 Incorrect 36 ms 604 KB Output isn't correct
9 Incorrect 48 ms 1652 KB Output isn't correct
10 Incorrect 66 ms 1640 KB Output isn't correct
11 Incorrect 98 ms 2184 KB Output isn't correct
12 Incorrect 135 ms 3368 KB Output isn't correct
13 Incorrect 135 ms 2828 KB Output isn't correct
14 Incorrect 441 ms 3244 KB Output isn't correct
15 Incorrect 582 ms 9436 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8067 ms 9216 KB Time limit exceeded
2 Execution timed out 8073 ms 7136 KB Time limit exceeded
3 Execution timed out 8067 ms 12788 KB Time limit exceeded
4 Incorrect 228 ms 4756 KB Output isn't correct
5 Incorrect 348 ms 8988 KB Output isn't correct
6 Execution timed out 8089 ms 21352 KB Time limit exceeded
7 Execution timed out 8080 ms 35728 KB Time limit exceeded
8 Execution timed out 8093 ms 36188 KB Time limit exceeded
9 Incorrect 1279 ms 24748 KB Output isn't correct
10 Execution timed out 8084 ms 52884 KB Time limit exceeded
11 Incorrect 1935 ms 28980 KB Output isn't correct
12 Incorrect 4325 ms 25144 KB Output isn't correct
13 Execution timed out 8052 ms 23172 KB Time limit exceeded
14 Execution timed out 8085 ms 28964 KB Time limit exceeded
15 Execution timed out 8090 ms 28140 KB Time limit exceeded
16 Execution timed out 8050 ms 36172 KB Time limit exceeded
17 Execution timed out 8099 ms 42616 KB Time limit exceeded