oj.uz

Submission #896396

# Submission time Handle Problem Language Result Execution time Memory
896396 2024-01-01T11:16:09 Z arashMLG Regions (IOI09_regions) C++17
90 / 100
 3525 ms 131072 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int sq = 300;
const int N = 2e5 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


struct Fen {
	int bit[N];
	
	void add(int pos,int x) {
		for(; pos < N; pos += pos&-pos)
			bit[pos] += x;
	}
	
	void add(int l,int r,int x) {
		add(l,x);
		add(r+1,-x);
	}
	
	int get(int pos) {
		int ans=0;
		for(; pos > 0 ; pos -= pos&-pos)
			ans += bit[pos];
		return ans;
	}
} fen;

int n,r,q;
vector<int> G[N];
int psu[N],psd[N];
int h[N];
vector<int> com[N];
unordered_map<int,int,custom_hash> mp[N];
int st[N],ft[N];
int timer = 1;

void dfsset(int v) {
	st[v] = timer ++;
	for(int u : G[v]) dfsset(u);
	ft[v] = timer-1;
}

void dfs(int v,int cur_r) {
	psu[v] += (h[v] == cur_r);
	psd[v] = (h[v] == cur_r);
	
	for(int u : G[v]) {
		psu[u] = psu[v];
		dfs(u,cur_r);
		psd[v] += psd[u];
	}
	if(sz(com[h[v]]) < sq || h[v] > cur_r) {
		mp[cur_r][h[v]] += psu[v];
		mp[h[v]][cur_r] += psd[v];
	}
	if(v == 1) psu[v] = psd[v] = 0;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>r>>q;
	for(int i = 1; i <= n ; i++) {
		if(i >= 2) {
			int p; cin>>p;
			G[p].pb(i);
		}
		cin>>h[i];
		com[h[i]].pb(i);
		
	}
	dfsset(1);
	for(int i = 1; i<= r; i ++) {
		if(sz(com[i]) >= sq) {
			dfs(1,i);
		}
	}
	while(q--) {
		int r1,r2; cin>>r1>>r2;
		if(sz(com[r1]) >= sq || sz(com[r2]) >= sq){
			cout<<mp[r1][r2] << endl;
			continue;
		}
		int ans=0;
		for(int x : com[r1]) {
			fen.add(st[x],ft[x],1);
		}
		for(int x : com[r2]) {
			ans += fen.get(st[x]);
		}
		for(int x : com[r1]) {
			fen.add(st[x],ft[x],-1);
		}
		cout<<ans << endl;
	}
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 7 ms 24920 KB Output is correct
4 Correct 7 ms 24920 KB Output is correct
5 Correct 9 ms 24920 KB Output is correct
6 Correct 15 ms 24920 KB Output is correct
7 Correct 20 ms 24920 KB Output is correct
8 Correct 24 ms 24920 KB Output is correct
9 Correct 43 ms 25432 KB Output is correct
10 Correct 69 ms 25272 KB Output is correct
11 Correct 124 ms 25524 KB Output is correct
12 Correct 127 ms 25944 KB Output is correct
13 Correct 183 ms 25688 KB Output is correct
14 Correct 316 ms 26200 KB Output is correct
15 Correct 390 ms 27736 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1264 ms 29532 KB Output is correct
2 Correct 1403 ms 27608 KB Output is correct
3 Correct 2721 ms 31268 KB Output is correct
4 Correct 324 ms 26052 KB Output is correct
5 Correct 319 ms 27324 KB Output is correct
6 Correct 798 ms 61720 KB Output is correct
7 Correct 1196 ms 68024 KB Output is correct
8 Correct 2041 ms 114888 KB Output is correct
9 Correct 3525 ms 90860 KB Output is correct
10 Runtime error 1061 ms 131072 KB Execution killed with signal 9
11 Runtime error 1831 ms 131072 KB Execution killed with signal 9
12 Correct 1267 ms 36436 KB Output is correct
13 Correct 1854 ms 37128 KB Output is correct
14 Correct 2550 ms 64016 KB Output is correct
15 Correct 3213 ms 45312 KB Output is correct
16 Correct 3140 ms 54584 KB Output is correct
17 Correct 3250 ms 79172 KB Output is correct