oj.uz

답안 #655607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655607 2022-11-05T00:28:30 Z rafatoa Regions (IOI09_regions) C++17
12 / 100
 8000 ms 131072 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 = 100;
	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
7.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 7 ms 336 KB Output is correct
6 Incorrect 20 ms 532 KB Output isn't correct
7 Incorrect 27 ms 732 KB Output isn't correct
8 Incorrect 15 ms 596 KB Output isn't correct
9 Incorrect 36 ms 1640 KB Output isn't correct
10 Incorrect 77 ms 1608 KB Output isn't correct
11 Incorrect 98 ms 2148 KB Output isn't correct
12 Incorrect 107 ms 3396 KB Output isn't correct
13 Incorrect 156 ms 2940 KB Output isn't correct
14 Correct 1260 ms 8000 KB Output is correct
15 Correct 2735 ms 16176 KB Output is correct

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4676 ms 13688 KB Output is correct
2 Execution timed out 8015 ms 11304 KB Time limit exceeded
3 Execution timed out 8073 ms 21000 KB Time limit exceeded
4 Incorrect 2448 ms 39236 KB Output isn't correct
5 Incorrect 2568 ms 25192 KB Output isn't correct
6 Execution timed out 8021 ms 22080 KB Time limit exceeded
7 Execution timed out 8048 ms 40732 KB Time limit exceeded
8 Execution timed out 8012 ms 57136 KB Time limit exceeded
9 Execution timed out 8038 ms 124460 KB Time limit exceeded
10 Execution timed out 8064 ms 102764 KB Time limit exceeded
11 Execution timed out 8074 ms 61544 KB Time limit exceeded
12 Execution timed out 8099 ms 85392 KB Time limit exceeded
13 Execution timed out 8074 ms 118128 KB Time limit exceeded
14 Execution timed out 8087 ms 96700 KB Time limit exceeded
15 Runtime error 6984 ms 131072 KB Execution killed with signal 9
16 Execution timed out 8100 ms 123712 KB Time limit exceeded
17 Execution timed out 8048 ms 126648 KB Time limit exceeded