제출 #490677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490677		Karliver	Regions (IOI09_regions)	C++17	35 / 100	5459 ms	46348 KiB

regions

	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int MX = 2e5 + 10;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int _n) {
        this->n = _n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
int N, R, Q;
bool ishe[MX];
V<int> heavy;
V<int> g[MX];
int tin[MX], tout[MX];
int T = 1;
void dfs(int v) {
	tin[v] = T++;
	for(auto c : g[v])
		dfs(c);
	tout[v] = T - 1;
}
V<int> rg[25002];
V<ll> FT[25002];
V<ll> TF[25002];
const int B = 420;
void solve() {

	cin >> N >> R >> Q;

	int a, b;
	cin >> a;
	rg[a].push_back(1);	

	for(int i = 2;i <= N;++i) {
		
		cin >> a >> b;
		g[a].push_back(i);
		rg[b].push_back(i);
	}
	dfs(1);
	FenwickTree F(N + 1);

	
	for(int i = 1;i <= R;++i) {
		if(sz(rg[i]) < B)
			continue;
		ishe[i] = 1;
		for(auto c : rg[i])
			F.add(tin[c], 1);
		TF[i].resize(R + 1);
		for(int j = 1;j <= R;++j) {
			for(auto x : rg[j]) {
				TF[i][j] += F.sum(tin[x], tout[x]);
			}
		}
		for(auto c : rg[i])
			F.add(tin[c], -1);
		for(int j = 1;j <= R;++j) {
			if(j == i)continue;
			for(auto x : rg[j])
				F.add(tin[x], 1);

			for(auto c : rg[i])
				FT[i][j] += F.sum(tin[c], tout[c]);

			for(auto x : rg[j])
				F.add(tin[x], -1);
		}
	}

	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;

		if(ishe[r2]) {
			cout << TF[r2][r1] << endl;
			continue;
		}
		if(ishe[r1]) {
			cout << FT[r1][r2] << endl;
			continue;
		}
		for(auto c : rg[r2])
			F.add(tin[c], 1);
		int ret = 0;
		for(auto c : rg[r1])
			ret += F.sum(tin[c], tout[c]);

		cout << ret << endl;
		for(auto c : rg[r2])
			F.add(tin[c], -1);
	}




	



}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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