제출 #490681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490681		Karliver	Regions (IOI09_regions)	C++14	100 / 100	4460 ms	40932 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);
}

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];
int H[MX];
const int B = 420;
int X;
void SC(int v, int rr) {
	FT[rr][H[v]] += X;
	if(H[v] == rr)
		++X;
	for(auto c : g[v]) {
		SC(c, rr);
	}
	if(H[v] == rr)
		--X;
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
V<int> kk[25001];
void solve() {

	cin >> N >> R >> Q;

	int a, b;
	cin >> a;
	rg[a].push_back(1);	
	H[1] = a;
	for(int i = 2;i <= N;++i) {
		
		cin >> a >> b;
		g[a].push_back(i);
		rg[b].push_back(i);
		H[i] = b;
	}
	dfs(1);
	
	
	for(int i = 1;i <= R;++i) {
		for(auto c : rg[i])
			kk[i].push_back(tin[c]);
		sort(all(kk[i]));
	}
	for(int i= 1;i <= R;++i) {
		if(sz(rg[i]) < B)
			continue;
		ishe[i] = 1;
		FT[i].resize(R + 1);
		X = 0;
		SC(1, i);
	}

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

		
		if(ishe[r1]) {
			cout << FT[r1][r2] << endl;
			continue;
		}
		int ret = 0;
		//debug(rg[r1], r1);
		for(auto c : rg[r1]) {
			int rb = upper_bound(all(kk[r2]), tout[c]) - kk[r2].begin();
			int lb = lower_bound(all(kk[r2]), tin[c]) - kk[r2].begin();
			ret += rb - lb;
		}
		cout << ret << endl;
	}




	



}
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: 85 / 85