oj.uz

Submission #722452

# Submission time Handle Problem Language Result Execution time Memory
722452 2023-04-12T02:53:21 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 6 ms 10192 KB Output is correct
3 Correct 7 ms 10212 KB Output is correct
4 Correct 10 ms 10320 KB Output is correct
5 Correct 13 ms 10300 KB Output is correct
6 Correct 20 ms 10320 KB Output is correct
7 Correct 30 ms 10320 KB Output is correct
8 Correct 32 ms 10432 KB Output is correct
9 Correct 40 ms 10704 KB Output is correct
10 Correct 100 ms 10832 KB Output is correct
11 Correct 127 ms 11108 KB Output is correct
12 Correct 139 ms 11648 KB Output is correct
13 Correct 269 ms 11344 KB Output is correct
14 Correct 317 ms 11984 KB Output is correct
15 Correct 270 ms 13904 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2174 ms 15712 KB Output isn't correct
2 Incorrect 2497 ms 14664 KB Output isn't correct
3 Incorrect 3452 ms 17648 KB Output isn't correct
4 Correct 247 ms 12112 KB Output is correct
5 Correct 338 ms 13284 KB Output is correct
6 Runtime error 709 ms 59096 KB Execution killed with signal 11
7 Correct 1846 ms 14392 KB Output is correct
8 Incorrect 1501 ms 25492 KB Output isn't correct
9 Correct 2419 ms 19936 KB Output is correct
10 Correct 3929 ms 23940 KB Output is correct
11 Correct 4408 ms 20356 KB Output is correct
12 Execution timed out 8045 ms 52064 KB Time limit exceeded
13 Runtime error 7175 ms 111764 KB Execution killed with signal 11
14 Runtime error 7862 ms 127236 KB Execution killed with signal 11
15 Runtime error 3775 ms 131072 KB Execution killed with signal 11
16 Runtime error 2362 ms 131072 KB Execution killed with signal 11
17 Runtime error 2189 ms 131072 KB Execution killed with signal 11