oj.uz

Submission #722468

# Submission time Handle Problem Language Result Execution time Memory
722468 2023-04-12T03:30:53 Z ono_de206 Regions (IOI09_regions) C++14
45 / 100
 7961 ms 131072 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 = 500;
int cnt[510][25010], in[mxn], out[mxn], tt, kk[mxn], 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) {
	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;
	for(int i = 1; i<= n; i++) {
		if(i == 1)
			cin >> h[i];
		else
			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[h[i]].size() >= B) {
			kk[i] = ++tt;
			solve(1, 0, i);
		}
		sort(all(d[i]));
	}
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if(p[r1].size() >= B) {
			cout << cnt[kk[r1]][r2] << '\n';
		}
		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';
		}
		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 4 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 7 ms 6096 KB Output is correct
5 Correct 11 ms 6224 KB Output is correct
6 Correct 24 ms 6224 KB Output is correct
7 Correct 29 ms 6224 KB Output is correct
8 Correct 35 ms 6224 KB Output is correct
9 Correct 45 ms 6620 KB Output is correct
10 Correct 58 ms 6736 KB Output is correct
11 Correct 135 ms 6992 KB Output is correct
12 Correct 151 ms 7420 KB Output is correct
13 Correct 185 ms 7288 KB Output is correct
14 Correct 228 ms 7840 KB Output is correct
15 Correct 231 ms 9760 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1904 ms 11676 KB Output isn't correct
2 Incorrect 2364 ms 10396 KB Output isn't correct
3 Incorrect 2933 ms 13528 KB Output isn't correct
4 Correct 286 ms 7888 KB Output is correct
5 Correct 335 ms 9160 KB Output is correct
6 Runtime error 635 ms 51196 KB Execution killed with signal 11
7 Correct 1714 ms 10340 KB Output is correct
8 Incorrect 1453 ms 21220 KB Output isn't correct
9 Correct 2151 ms 15892 KB Output is correct
10 Correct 4595 ms 19852 KB Output is correct
11 Correct 3748 ms 16208 KB Output is correct
12 Runtime error 7961 ms 104252 KB Execution killed with signal 11
13 Runtime error 5461 ms 104652 KB Execution killed with signal 11
14 Runtime error 7019 ms 120552 KB Execution killed with signal 11
15 Runtime error 3741 ms 131072 KB Execution killed with signal 11
16 Runtime error 2358 ms 131072 KB Execution killed with signal 11
17 Runtime error 2223 ms 131072 KB Execution killed with signal 11