oj.uz

Submission #722455

# Submission time Handle Problem Language Result Execution time Memory
722455 2023-04-12T02:55:45 Z ono_de206 Regions (IOI09_regions) C++14
35 / 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 = 400;
int cnt[500][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 7 ms 10192 KB Output is correct
2 Correct 6 ms 10192 KB Output is correct
3 Correct 7 ms 10192 KB Output is correct
4 Correct 9 ms 10320 KB Output is correct
5 Correct 12 ms 10320 KB Output is correct
6 Correct 21 ms 10344 KB Output is correct
7 Correct 29 ms 10320 KB Output is correct
8 Correct 46 ms 10348 KB Output is correct
9 Correct 42 ms 10664 KB Output is correct
10 Correct 94 ms 10912 KB Output is correct
11 Correct 119 ms 11088 KB Output is correct
12 Correct 166 ms 11588 KB Output is correct
13 Correct 190 ms 11380 KB Output is correct
14 Correct 306 ms 12028 KB Output is correct
15 Correct 254 ms 13976 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2183 ms 15740 KB Output isn't correct
2 Incorrect 2315 ms 14612 KB Output isn't correct
3 Incorrect 2985 ms 17568 KB Output isn't correct
4 Correct 213 ms 12004 KB Output is correct
5 Correct 309 ms 13264 KB Output is correct
6 Runtime error 647 ms 58960 KB Execution killed with signal 11
7 Runtime error 916 ms 73108 KB Execution killed with signal 11
8 Runtime error 812 ms 83420 KB Execution killed with signal 11
9 Correct 2153 ms 20040 KB Output is correct
10 Runtime error 1773 ms 131072 KB Execution killed with signal 11
11 Correct 4392 ms 20468 KB Output is correct
12 Execution timed out 8010 ms 51936 KB Time limit exceeded
13 Runtime error 5477 ms 111708 KB Execution killed with signal 11
14 Execution timed out 8045 ms 61900 KB Time limit exceeded
15 Runtime error 3851 ms 131072 KB Execution killed with signal 11
16 Runtime error 2372 ms 131072 KB Execution killed with signal 11
17 Runtime error 2132 ms 131072 KB Execution killed with signal 11