Submission #539183

#	Time	Username	Problem	Language	Result	Execution time	Memory
539183		fcw	Regions (IOI09_regions)	C++17	100 / 100	4119 ms	38340 KiB

regions

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

template<class T> struct segtree_range {
    int H, N;
    vector<T> ts;
    segtree_range() {}
    explicit segtree_range(int N_) {
	for (H = 0, N = 1; N < N_; ++H, N *= 2) {}
        ts.resize(2*N);
    }
    template<class Q> explicit segtree_range(const vector<Q>& qs) {
        const int N_ = int(qs.size());
        for (H = 1, N = 1; N < N_; ++H, N *= 2) {}
        ts.resize(2*N);
        for (int i = 0; i < N_; ++i) at(i) = T(qs[i]);
        build();
    }
    T& at(int a) { return ts[a + N]; }
    void build() { for (int a = N; --a; ) merge(a); }
    inline void push(int a) { ts[a].push(ts[2 * a], ts[2 * a + 1]); }
    inline void merge(int a) { ts[a].merge(ts[2*a], ts[2*a+1]); }
    void for_parents_down(int a, int b) {
        for (int h = H; h; --h) {
            const int l = (a >> h), r = (b >> h);
            if (l == r) {
                if ((l << h) != a || (r << h) != b) push(l);
            } else {
                if ((l << h) != a) push(l);
                if ((r << h) != b) push(r);
            }
        }
    }
    void for_parents_up(int a, int b) {
        for (int h = 1; h <= H; ++h) {
            const int l = (a >> h), r = (b >> h);
            if (l == r) {
                if ((l << h) != a || (r << h) != b) merge(l);
            } else {
                if ((l << h) != a) merge(l);
                if ((r << h) != b) merge(r);
            }
        }
    }
    template<class F, class... Args> void update(int a, int b, F f, Args&&... args) {
        if (a == b) return;
        a += N; b += N;
        for_parents_down(a, b);
        for (int l = a, r = b; l < r; l /= 2, r /= 2) {
            if (l & 1) (ts[l++].*f)(args...);
            if (r & 1) (ts[--r].*f)(args...);
        }
        for_parents_up(a, b);
    }
    T query(int a, int b) {
        if (a == b) return T();
        a += N; b += N;
        for_parents_down(a, b);
        T lhs, rhs, t;
        for (int l = a, r = b; l < r; l /= 2, r /= 2) {
            if (l & 1) { t.merge(lhs, ts[l++]); lhs = t; }
            if (r & 1) { t.merge(ts[--r], rhs); rhs = t; }
        }
        t.merge(lhs, rhs); return t;
    }
    template<class Op, class E, class F, class... Args>
        auto query(int a, int b, Op op, E e, F f, Args&&... args) {
        if (a == b) return e();
        a += N; b += N;
        for_parents_down(a, b);
        auto lhs = e(), rhs = e();
        for (int l = a, r = b; l < r; l /= 2, r /= 2) {
            if (l & 1) lhs = op(lhs, (ts[l++].*f)(args...));
            if (r & 1) rhs = op((ts[--r].*f)(args...), rhs);
        }
        return op(lhs, rhs);
    }
    // find min i s.t. T::f(args...) returns true in [a, i) from left to right
    template<class F, class... Args> int find_right(int a, F f, Args &&... args) {
	assert(0 <= a && a <= N);
	if ((T().*f)(args...)) return a;
	if (a == N) return 1 + N;
	a += N;
        for (int h = H; h; --h) push(a >> h);
	for (; ; a /= 2) if (a & 1) {
	    if ((ts[a].*f)(args...)) {
		for (; a < N; ) {
                    push(a);
		    if (!(ts[a <<= 1].*f)(args...)) ++a;
		}
		return a - N + 1;
	    }
	    ++a;
	    if (!(a & (a - 1))) return N + 1;
	}
    }
    // find max i s.t. T::f(args...) returns true in [i, a) from right to left
    template<class F, class... Args> int find_left(int a, F f, Args &&... args) {
	assert(0 <= a && a <= N);
	if ((T().*f)(args...)) return a;
	if (a == 0) return -1;
	a += N;
        for (int h = H; h; --h) push((a - 1) >> h);
	for (; ; a /= 2) if ((a & 1) || a == 2) {
	    if ((ts[a - 1].*f)(args...)) {
		for (; a <= N; ) {
                    push(a - 1);
		    if (!(ts[(a <<= 1) - 1].*f)(args...)) --a;
		}
		return a - N - 1;
	    }
	    --a;
	    if (!(a & (a - 1))) return -1;
	}
    }
};

template<typename T>struct seg_node{
	T val;
	seg_node(T n = 0): val(n){}
	void push(seg_node& l, seg_node& r){
	}
	void merge(const seg_node& l, const seg_node& r){
		val = l.val + r.val;
	}
	void add(T n){
		val += n;
	}
	T get_sum(){ return val; }
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	//ifstream cin;
	//cin.open("promote.in");
	//ofstream cout;
	//cout.open("promote.out");
	int n, r, q;
	cin>>n>>r>>q;
	vector<vector<int>>g(n);
	vector<int>p(n), h(n);
	cin>>h[0]; h[0]--;
	for(int i=1;i<n;i++){
		cin>>p[i]>>h[i];
		p[i]--, h[i]--;
		g[p[i]].push_back(i);
	}

	vector<vector<int>>reg(r);
	for(int i=0;i<n;i++) reg[h[i]].push_back(i);
	int SZ = sqrt(n);
	vector<vector<int>>prep(r);
	vector<int>heavy;
	for(int i=0;i<r;i++){
		if((int)reg[i].size() > SZ){
			prep[i] = vector<int>(r);
			heavy.push_back(i);
		}
	}

	vector<int>tin(n), tout(n), cnt(r);
	vector<vector<int>>v(n);
	int timer = 0;
	auto dfs = [&](auto& self, int u, int p)->void{
		tin[u] = timer++;
		v[h[u]].push_back(tin[u]);
		cnt[h[u]]++;
		for(int nxt : g[u]){
			if(nxt == p) continue;
			self(self, nxt, u);
		}
		tout[u] = timer;
		cnt[h[u]]--;
		for(int c : heavy){
			if(h[u] == c) continue;
			prep[c][h[u]] += cnt[c];
		}
	};
	dfs(dfs, 0, 0);
	for(int i=0;i<q;i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		if(!prep[a].empty()){
			cout<<prep[a][b]<<endl;
		}
		else{
			int ans = 0;
			for(int u : reg[a]){
				ans += int(lower_bound(v[b].begin(), v[b].end(), tout[u]) -
				lower_bound(v[b].begin(), v[b].end(), tin[u]));
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85