oj.uz

Submission #490681

# Submission time Handle Problem Language Result Execution time Memory
490681 2021-11-28T16:06:42 Z Karliver Regions (IOI09_regions) C++14
100 / 100
 4460 ms 40932 KB 
	
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 4 ms 6728 KB Output is correct
3 Correct 6 ms 6668 KB Output is correct
4 Correct 8 ms 6728 KB Output is correct
5 Correct 9 ms 6728 KB Output is correct
6 Correct 16 ms 6856 KB Output is correct
7 Correct 32 ms 6856 KB Output is correct
8 Correct 40 ms 6856 KB Output is correct
9 Correct 53 ms 7112 KB Output is correct
10 Correct 94 ms 7240 KB Output is correct
11 Correct 136 ms 7496 KB Output is correct
12 Correct 136 ms 8008 KB Output is correct
13 Correct 191 ms 7752 KB Output is correct
14 Correct 257 ms 8296 KB Output is correct
15 Correct 247 ms 10184 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1810 ms 11380 KB Output is correct
2 Correct 2177 ms 10164 KB Output is correct
3 Correct 2454 ms 13120 KB Output is correct
4 Correct 249 ms 8392 KB Output is correct
5 Correct 401 ms 9544 KB Output is correct
6 Correct 547 ms 12940 KB Output is correct
7 Correct 1339 ms 12492 KB Output is correct
8 Correct 1059 ms 23560 KB Output is correct
9 Correct 2321 ms 15768 KB Output is correct
10 Correct 2949 ms 40932 KB Output is correct
11 Correct 4460 ms 15888 KB Output is correct
12 Correct 1065 ms 17632 KB Output is correct
13 Correct 1967 ms 17828 KB Output is correct
14 Correct 2461 ms 20992 KB Output is correct
15 Correct 3202 ms 22120 KB Output is correct
16 Correct 2599 ms 27524 KB Output is correct
17 Correct 2746 ms 29772 KB Output is correct