oj.uz

Submission #896402

# Submission time Handle Problem Language Result Execution time Memory
896402 2024-01-01T11:22:02 Z arashMLG Regions (IOI09_regions) C++17
100 / 100
 5566 ms 63384 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 = 1200;
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 4 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 22872 KB Output is correct
5 Correct 10 ms 22872 KB Output is correct
6 Correct 12 ms 22872 KB Output is correct
7 Correct 18 ms 22872 KB Output is correct
8 Correct 22 ms 23128 KB Output is correct
9 Correct 36 ms 23384 KB Output is correct
10 Correct 59 ms 23384 KB Output is correct
11 Correct 108 ms 23640 KB Output is correct
12 Correct 123 ms 23896 KB Output is correct
13 Correct 170 ms 23684 KB Output is correct
14 Correct 271 ms 24152 KB Output is correct
15 Correct 368 ms 25808 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1352 ms 27296 KB Output is correct
2 Correct 1364 ms 25636 KB Output is correct
3 Correct 2512 ms 30200 KB Output is correct
4 Correct 298 ms 24072 KB Output is correct
5 Correct 349 ms 25460 KB Output is correct
6 Correct 1349 ms 25172 KB Output is correct
7 Correct 1923 ms 25876 KB Output is correct
8 Correct 2003 ms 29424 KB Output is correct
9 Correct 2762 ms 30092 KB Output is correct
10 Correct 5566 ms 33332 KB Output is correct
11 Correct 4546 ms 29168 KB Output is correct
12 Correct 1219 ms 33920 KB Output is correct
13 Correct 1788 ms 34852 KB Output is correct
14 Correct 2822 ms 45612 KB Output is correct
15 Correct 3135 ms 42948 KB Output is correct
16 Correct 3071 ms 54128 KB Output is correct
17 Correct 3681 ms 63384 KB Output is correct