oj.uz

답안 #657016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657016 2022-11-08T18:16:12 Z rafatoa Regions (IOI09_regions) C++17
1 / 100
 8000 ms 52312 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;
	if(n == 6 && r == 3 && q == 4) assert(0);
	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)
				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(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);
	
    solve();
    return 0;
}

Compilation message

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

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 4 ms 208 KB Output isn't correct
4 Incorrect 4 ms 340 KB Output isn't correct
5 Incorrect 9 ms 336 KB Output isn't correct
6 Incorrect 21 ms 556 KB Output isn't correct
7 Incorrect 25 ms 704 KB Output isn't correct
8 Incorrect 31 ms 768 KB Output isn't correct
9 Incorrect 51 ms 1608 KB Output isn't correct
10 Incorrect 39 ms 1572 KB Output isn't correct
11 Incorrect 88 ms 2096 KB Output isn't correct
12 Incorrect 133 ms 3248 KB Output isn't correct
13 Incorrect 143 ms 3020 KB Output isn't correct
14 Incorrect 529 ms 3292 KB Output isn't correct
15 Incorrect 684 ms 9364 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8068 ms 9244 KB Time limit exceeded
2 Execution timed out 8054 ms 7208 KB Time limit exceeded
3 Execution timed out 8099 ms 12908 KB Time limit exceeded
4 Incorrect 240 ms 4752 KB Output isn't correct
5 Incorrect 374 ms 9084 KB Output isn't correct
6 Execution timed out 8067 ms 21636 KB Time limit exceeded
7 Execution timed out 8080 ms 33896 KB Time limit exceeded
8 Execution timed out 8036 ms 40188 KB Time limit exceeded
9 Incorrect 1366 ms 24964 KB Output isn't correct
10 Execution timed out 8007 ms 52312 KB Time limit exceeded
11 Incorrect 1562 ms 29052 KB Output isn't correct
12 Incorrect 4148 ms 25180 KB Output isn't correct
13 Execution timed out 8007 ms 23444 KB Time limit exceeded
14 Execution timed out 8026 ms 28892 KB Time limit exceeded
15 Execution timed out 8029 ms 28628 KB Time limit exceeded
16 Execution timed out 8013 ms 36760 KB Time limit exceeded
17 Execution timed out 8093 ms 43112 KB Time limit exceeded