oj.uz

Submission #722473

# Submission time Handle Problem Language Result Execution time Memory
722473 2023-04-12T03:49:25 Z ono_de206 Regions (IOI09_regions) C++14
100 / 100
 4758 ms 31024 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, B = 400;
int cnt[610][25010], in[mxn], out[mxn], tt, kk[25010], s[mxn], h[mxn];
vector<int> g[mxn], p[25010], d[25010];

void dfs(int to) {
	in[to] = ++tt;
	d[h[to]].pb(in[to]);
	for(int x : g[to]) {
		dfs(x);
	}
	out[to] = tt;
}

void solve(int to, int cn, int id) {
	if (kk[id] > 600) exit(1);
	cnt[kk[id]][h[to]] += cn;
	cn += (h[to] == id);
	for(int x : g[to]) {
		solve(x, cn, id);
	}
	cn -= (h[to] == id);
}

void go() {
	int n, r, q;
	cin >> n >> r >> q;
	// scanf("%d %d %d", &n, &r, &q);
	for(int i = 1; i<= n; i++) {
		if(i == 1)
			// scanf("%d", &h[i]);
			cin >> h[i];
		else
			// scanf("%d %d", &s[i], &h[i]);
			cin >> s[i] >> h[i];
		p[h[i]].pb(i);
		if(i > 1) g[s[i]].pb(i);
	}
	dfs(1);
	tt = 0;
	for(int i = 1; i <= r; i++) {
		if(p[i].size() >= B) {
			kk[i] = ++tt;
			solve(1, 0, i);
		}
		sort(all(d[i]));
	}
	assert(tt <= 600);
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		// scanf("%d %d", &r1, &r2);
		if(p[r1].size() >= B) {
			cout << cnt[kk[r1]][r2] << '\n';
			// printf("%d\n", cnt[kk[r1]][r2]);
		}
		else {
			int ans = 0;
			for(int x : p[r1]) {
				int ll = lower_bound(all(d[r2]), in[x]) - d[r2].begin();
				int rr = upper_bound(all(d[r2]), out[x]) - d[r2].begin();
				ans += rr - ll;
			}
			cout << ans << '\n';
			// printf("%d\n", ans);
		}
		// fflush(stdout);
		cout.flush();
	}
}
 
signed main() {
	// #ifndef
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6168 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 9 ms 6224 KB Output is correct
6 Correct 19 ms 6288 KB Output is correct
7 Correct 29 ms 6224 KB Output is correct
8 Correct 35 ms 6224 KB Output is correct
9 Correct 48 ms 6608 KB Output is correct
10 Correct 77 ms 6736 KB Output is correct
11 Correct 130 ms 6992 KB Output is correct
12 Correct 151 ms 7504 KB Output is correct
13 Correct 183 ms 7248 KB Output is correct
14 Correct 280 ms 7876 KB Output is correct
15 Correct 266 ms 9808 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 11240 KB Output is correct
2 Correct 1943 ms 10072 KB Output is correct
3 Correct 2671 ms 13052 KB Output is correct
4 Correct 273 ms 7888 KB Output is correct
5 Correct 358 ms 9192 KB Output is correct
6 Correct 561 ms 11184 KB Output is correct
7 Correct 1312 ms 11580 KB Output is correct
8 Correct 1084 ms 19828 KB Output is correct
9 Correct 2283 ms 15844 KB Output is correct
10 Correct 2646 ms 31024 KB Output is correct
11 Correct 4758 ms 16244 KB Output is correct
12 Correct 1527 ms 17768 KB Output is correct
13 Correct 2141 ms 17952 KB Output is correct
14 Correct 2505 ms 19580 KB Output is correct
15 Correct 3572 ms 22304 KB Output is correct
16 Correct 2998 ms 27540 KB Output is correct
17 Correct 3211 ms 28128 KB Output is correct