Submission #896395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896395	2024-01-01T11:15:27 Z	arashMLG	Regions (IOI09_regions)	C++17	100 / 100	5669 ms	68512 KB

regions

#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 = 1000;
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	6 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	9 ms	24920 KB	Output is correct
6	Correct	12 ms	24920 KB	Output is correct
7	Correct	17 ms	24920 KB	Output is correct
8	Correct	27 ms	25176 KB	Output is correct
9	Correct	34 ms	25432 KB	Output is correct
10	Correct	60 ms	25432 KB	Output is correct
11	Correct	113 ms	25688 KB	Output is correct
12	Correct	121 ms	25944 KB	Output is correct
13	Correct	165 ms	25640 KB	Output is correct
14	Correct	261 ms	26080 KB	Output is correct
15	Correct	343 ms	27736 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1313 ms	28868 KB	Output is correct
2	Correct	1355 ms	27308 KB	Output is correct
3	Correct	2417 ms	31304 KB	Output is correct
4	Correct	328 ms	26008 KB	Output is correct
5	Correct	307 ms	27224 KB	Output is correct
6	Correct	1434 ms	26972 KB	Output is correct
7	Correct	2031 ms	27720 KB	Output is correct
8	Correct	2045 ms	31108 KB	Output is correct
9	Correct	3089 ms	31228 KB	Output is correct
10	Correct	5669 ms	34788 KB	Output is correct
11	Correct	4762 ms	30816 KB	Output is correct
12	Correct	1299 ms	36436 KB	Output is correct
13	Correct	1802 ms	37120 KB	Output is correct
14	Correct	3258 ms	50532 KB	Output is correct
15	Correct	3779 ms	45472 KB	Output is correct
16	Correct	3881 ms	54584 KB	Output is correct
17	Correct	3828 ms	68512 KB	Output is correct