oj.uz

Submission #746546

# Submission time Handle Problem Language Result Execution time Memory
746546 2023-05-22T17:44:42 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
60 / 100
 8000 ms 32032 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end() 
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'

const int N = 200200, R = 25025;
int n, r, q, timer=0, tin[N], tout[N];
vector<int> adj[N], color[R];
indexed_set<int> b[R];

void dfs(int s=0, int e=-1) {
	tin[s] = timer++;
	for (int node:adj[s]) {
		if (node==e) continue;
		dfs(node,s);
	}
	tout[s] = timer;
}

int main() {
	// setIO("");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> r >> q;
	int l; cin >> l; color[l].pb(0);
	for (int i=1, s, e;i<=n-1;i++) {
		cin >> s >> e;
		s--;
		adj[s].pb(i), adj[i].pb(s);
		color[e].pb(i);
	}
	dfs();
	// for (int i = 0; i < n; i++)
	// 	cout << tin[i] << " " << tout[i] << nl;
	for (int i = 0; i < R; i++) {
		for (int j: color[i]) {
			b[i].insert(tin[j]);
		}	
	}
	while(q--) {
		int i, j; cin >> i >> j;
		int ans = 0;
		for (int parent:color[i]) {
			int hi = b[j].order_of_key(tout[parent]);
			int lo = b[j].order_of_key(tin[parent]);
			ans += (hi - lo);
		}
		cout << ans << endl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7452 KB Output is correct
2 Correct 5 ms 7504 KB Output is correct
3 Correct 9 ms 7504 KB Output is correct
4 Correct 10 ms 7488 KB Output is correct
5 Correct 13 ms 7504 KB Output is correct
6 Correct 18 ms 7632 KB Output is correct
7 Correct 29 ms 7632 KB Output is correct
8 Correct 44 ms 7760 KB Output is correct
9 Correct 55 ms 8144 KB Output is correct
10 Correct 90 ms 8400 KB Output is correct
11 Correct 168 ms 8916 KB Output is correct
12 Correct 178 ms 9552 KB Output is correct
13 Correct 231 ms 9724 KB Output is correct
14 Correct 439 ms 10332 KB Output is correct
15 Correct 309 ms 12496 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8086 ms 14792 KB Time limit exceeded
2 Execution timed out 8048 ms 14908 KB Time limit exceeded
3 Execution timed out 8053 ms 16804 KB Time limit exceeded
4 Correct 329 ms 10376 KB Output is correct
5 Correct 401 ms 11740 KB Output is correct
6 Correct 1732 ms 12488 KB Output is correct
7 Correct 2037 ms 14260 KB Output is correct
8 Correct 1573 ms 19020 KB Output is correct
9 Correct 2778 ms 22316 KB Output is correct
10 Correct 5214 ms 26312 KB Output is correct
11 Correct 6085 ms 26632 KB Output is correct
12 Correct 7839 ms 25220 KB Output is correct
13 Execution timed out 8038 ms 25628 KB Time limit exceeded
14 Execution timed out 8055 ms 26428 KB Time limit exceeded
15 Execution timed out 8055 ms 28404 KB Time limit exceeded
16 Execution timed out 8026 ms 32032 KB Time limit exceeded
17 Execution timed out 8045 ms 31224 KB Time limit exceeded