oj.uz

Submission #722462

# Submission time Handle Problem Language Result Execution time Memory
722462 2023-04-12T03:19:13 Z ono_de206 Regions (IOI09_regions) C++14
45 / 100
 8000 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[B][25010], in[mxn], out[mxn], tt, kk[25010], s[mxn], h[mxn];
vector<int> g[mxn], p[mxn], 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() - 1;
				int rr = upper_bound(all(d[r2]), out[x]) - d[r2].begin() - 1;
				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 6 ms 10192 KB Output is correct
2 Correct 5 ms 10192 KB Output is correct
3 Correct 8 ms 10320 KB Output is correct
4 Correct 13 ms 10400 KB Output is correct
5 Correct 13 ms 10320 KB Output is correct
6 Correct 21 ms 10444 KB Output is correct
7 Correct 31 ms 10320 KB Output is correct
8 Correct 40 ms 10448 KB Output is correct
9 Correct 60 ms 10704 KB Output is correct
10 Correct 90 ms 10832 KB Output is correct
11 Correct 127 ms 11088 KB Output is correct
12 Correct 150 ms 11600 KB Output is correct
13 Correct 193 ms 11388 KB Output is correct
14 Correct 309 ms 11984 KB Output is correct
15 Correct 292 ms 13904 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1808 ms 15860 KB Output isn't correct
2 Incorrect 2009 ms 14612 KB Output isn't correct
3 Incorrect 2951 ms 17608 KB Output isn't correct
4 Correct 292 ms 12012 KB Output is correct
5 Correct 361 ms 13288 KB Output is correct
6 Runtime error 699 ms 58980 KB Execution killed with signal 11
7 Correct 1925 ms 14408 KB Output is correct
8 Incorrect 1462 ms 25352 KB Output isn't correct
9 Correct 2404 ms 19984 KB Output is correct
10 Correct 4448 ms 23908 KB Output is correct
11 Correct 4136 ms 20356 KB Output is correct
12 Execution timed out 8039 ms 54724 KB Time limit exceeded
13 Runtime error 6189 ms 111676 KB Execution killed with signal 11
14 Execution timed out 8105 ms 62276 KB Time limit exceeded
15 Runtime error 3585 ms 131072 KB Execution killed with signal 11
16 Runtime error 2294 ms 131072 KB Execution killed with signal 11
17 Runtime error 2204 ms 131072 KB Execution killed with signal 11