oj.uz

답안 #655605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655605 2022-11-05T00:25:44 Z rafatoa Regions (IOI09_regions) C++17
1 / 100
 8000 ms 63620 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;
	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 ans[{i, h[s]}] += cnt;
			
			for(auto u:adj[s])
				dfs3(u, cnt);
		};
		dfs3(1, 0);
	}
 
	while(q--){
		int r1, r2; cin >> r1 >> r2;
		if(r1 > sq || r2 > sq){
			cout << ans[{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 0 ms 208 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 5 ms 336 KB Output isn't correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 9 ms 584 KB Output isn't correct
7 Incorrect 23 ms 604 KB Output isn't correct
8 Incorrect 35 ms 584 KB Output isn't correct
9 Incorrect 50 ms 1584 KB Output isn't correct
10 Incorrect 70 ms 1600 KB Output isn't correct
11 Incorrect 94 ms 2172 KB Output isn't correct
12 Incorrect 95 ms 3456 KB Output isn't correct
13 Incorrect 151 ms 2920 KB Output isn't correct
14 Incorrect 434 ms 3256 KB Output isn't correct
15 Incorrect 478 ms 9312 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8020 ms 9216 KB Time limit exceeded
2 Execution timed out 8005 ms 7324 KB Time limit exceeded
3 Execution timed out 8053 ms 12896 KB Time limit exceeded
4 Incorrect 288 ms 4660 KB Output isn't correct
5 Incorrect 182 ms 9052 KB Output isn't correct
6 Execution timed out 8082 ms 22428 KB Time limit exceeded
7 Execution timed out 8020 ms 63620 KB Time limit exceeded
8 Execution timed out 8057 ms 40196 KB Time limit exceeded
9 Incorrect 1322 ms 24824 KB Output isn't correct
10 Execution timed out 8070 ms 52068 KB Time limit exceeded
11 Incorrect 1701 ms 29060 KB Output isn't correct
12 Incorrect 4135 ms 23920 KB Output isn't correct
13 Execution timed out 8044 ms 24848 KB Time limit exceeded
14 Execution timed out 8092 ms 28856 KB Time limit exceeded
15 Execution timed out 8093 ms 28528 KB Time limit exceeded
16 Execution timed out 8093 ms 36224 KB Time limit exceeded
17 Execution timed out 8095 ms 42772 KB Time limit exceeded