oj.uz

Submission #896390

# Submission time Handle Problem Language Result Execution time Memory
896390 2024-01-01T11:04:43 Z arashMLG Regions (IOI09_regions) C++17
100 / 100
 5704 ms 75568 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

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

const int sq = 600;
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 7 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 6 ms 25004 KB Output is correct
4 Correct 7 ms 24920 KB Output is correct
5 Correct 7 ms 24920 KB Output is correct
6 Correct 14 ms 24920 KB Output is correct
7 Correct 19 ms 24920 KB Output is correct
8 Correct 22 ms 25176 KB Output is correct
9 Correct 37 ms 25432 KB Output is correct
10 Correct 59 ms 25684 KB Output is correct
11 Correct 108 ms 25528 KB Output is correct
12 Correct 110 ms 25952 KB Output is correct
13 Correct 165 ms 25948 KB Output is correct
14 Correct 302 ms 26212 KB Output is correct
15 Correct 353 ms 28072 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1292 ms 29152 KB Output is correct
2 Correct 1291 ms 27416 KB Output is correct
3 Correct 2515 ms 31508 KB Output is correct
4 Correct 273 ms 26200 KB Output is correct
5 Correct 317 ms 27344 KB Output is correct
6 Correct 1511 ms 26824 KB Output is correct
7 Correct 2036 ms 27640 KB Output is correct
8 Correct 2041 ms 31156 KB Output is correct
9 Correct 2924 ms 31292 KB Output is correct
10 Correct 5704 ms 35092 KB Output is correct
11 Correct 4523 ms 31096 KB Output is correct
12 Correct 1295 ms 36476 KB Output is correct
13 Correct 1711 ms 37112 KB Output is correct
14 Correct 2489 ms 59096 KB Output is correct
15 Correct 2930 ms 45264 KB Output is correct
16 Correct 3131 ms 54580 KB Output is correct
17 Correct 2987 ms 75568 KB Output is correct