oj.uz

Submission #896393

# Submission time Handle Problem Language Result Execution time Memory
896393 2024-01-01T11:06:31 Z arashMLG Regions (IOI09_regions) C++17
100 / 100
 4973 ms 75416 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 = 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 5 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 6 ms 24920 KB Output is correct
4 Correct 7 ms 24920 KB Output is correct
5 Correct 8 ms 24916 KB Output is correct
6 Correct 14 ms 24920 KB Output is correct
7 Correct 21 ms 24920 KB Output is correct
8 Correct 23 ms 24920 KB Output is correct
9 Correct 32 ms 25432 KB Output is correct
10 Correct 53 ms 25432 KB Output is correct
11 Correct 106 ms 25580 KB Output is correct
12 Correct 109 ms 25944 KB Output is correct
13 Correct 165 ms 25576 KB Output is correct
14 Correct 274 ms 26004 KB Output is correct
15 Correct 314 ms 27736 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 29152 KB Output is correct
2 Correct 1148 ms 27404 KB Output is correct
3 Correct 2260 ms 31288 KB Output is correct
4 Correct 262 ms 25992 KB Output is correct
5 Correct 291 ms 27224 KB Output is correct
6 Correct 1388 ms 26952 KB Output is correct
7 Correct 1879 ms 27484 KB Output is correct
8 Correct 1883 ms 31120 KB Output is correct
9 Correct 2694 ms 31216 KB Output is correct
10 Correct 4973 ms 34800 KB Output is correct
11 Correct 4472 ms 30740 KB Output is correct
12 Correct 1213 ms 36444 KB Output is correct
13 Correct 1645 ms 37116 KB Output is correct
14 Correct 2294 ms 59084 KB Output is correct
15 Correct 2942 ms 45276 KB Output is correct
16 Correct 2853 ms 54572 KB Output is correct
17 Correct 3030 ms 75416 KB Output is correct