oj.uz

Submission #896399

# Submission time Handle Problem Language Result Execution time Memory
896399 2024-01-01T11:19:59 Z arashMLG Regions (IOI09_regions) C++17
100 / 100
 5563 ms 76408 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 = 700;
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];
map<int,int> 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 5 ms 23032 KB Output is correct
2 Correct 4 ms 22872 KB Output is correct
3 Correct 5 ms 22872 KB Output is correct
4 Correct 7 ms 22996 KB Output is correct
5 Correct 8 ms 22952 KB Output is correct
6 Correct 12 ms 22872 KB Output is correct
7 Correct 21 ms 22992 KB Output is correct
8 Correct 22 ms 23128 KB Output is correct
9 Correct 35 ms 23384 KB Output is correct
10 Correct 58 ms 23384 KB Output is correct
11 Correct 95 ms 23640 KB Output is correct
12 Correct 116 ms 23896 KB Output is correct
13 Correct 155 ms 23680 KB Output is correct
14 Correct 265 ms 24152 KB Output is correct
15 Correct 332 ms 25992 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 27380 KB Output is correct
2 Correct 1217 ms 25624 KB Output is correct
3 Correct 2436 ms 30204 KB Output is correct
4 Correct 282 ms 24260 KB Output is correct
5 Correct 312 ms 25460 KB Output is correct
6 Correct 1477 ms 25108 KB Output is correct
7 Correct 1917 ms 25812 KB Output is correct
8 Correct 2025 ms 29488 KB Output is correct
9 Correct 2815 ms 29864 KB Output is correct
10 Correct 5563 ms 33196 KB Output is correct
11 Correct 4609 ms 29172 KB Output is correct
12 Correct 1258 ms 33920 KB Output is correct
13 Correct 1744 ms 34844 KB Output is correct
14 Correct 2875 ms 58416 KB Output is correct
15 Correct 3209 ms 43148 KB Output is correct
16 Correct 3112 ms 54128 KB Output is correct
17 Correct 3880 ms 76408 KB Output is correct