oj.uz

Submission #746545

# Submission time Handle Problem Language Result Execution time Memory
746545 2023-05-22T17:42:13 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
0 / 100
 94 ms 22692 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-1;
}

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]+1);
			int lo = b[j].order_of_key(tin[parent]);
			ans += (hi - lo);
		}
		cout << ans << endl;
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7504 KB Output isn't correct
2 Incorrect 5 ms 7504 KB Output isn't correct
3 Incorrect 5 ms 7504 KB Output isn't correct
4 Incorrect 6 ms 7504 KB Output isn't correct
5 Incorrect 6 ms 7504 KB Output isn't correct
6 Incorrect 7 ms 7632 KB Output isn't correct
7 Incorrect 9 ms 7632 KB Output isn't correct
8 Incorrect 10 ms 7760 KB Output isn't correct
9 Runtime error 11 ms 8156 KB Execution killed with signal 13
10 Runtime error 14 ms 8504 KB Execution killed with signal 13
11 Execution timed out 11 ms 8308 KB Time limit exceeded (wall clock)
12 Execution timed out 12 ms 8656 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 8872 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 8992 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 10712 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 29 ms 11332 KB Time limit exceeded (wall clock)
2 Execution timed out 28 ms 11328 KB Time limit exceeded (wall clock)
3 Execution timed out 31 ms 12616 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 9132 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 10064 KB Time limit exceeded (wall clock)
6 Execution timed out 26 ms 10128 KB Time limit exceeded (wall clock)
7 Execution timed out 35 ms 11068 KB Time limit exceeded (wall clock)
8 Execution timed out 47 ms 14280 KB Time limit exceeded (wall clock)
9 Execution timed out 65 ms 15312 KB Time limit exceeded (wall clock)
10 Execution timed out 56 ms 18428 KB Time limit exceeded (wall clock)
11 Execution timed out 79 ms 17376 KB Time limit exceeded (wall clock)
12 Execution timed out 86 ms 16344 KB Time limit exceeded (wall clock)
13 Execution timed out 79 ms 16840 KB Time limit exceeded (wall clock)
14 Execution timed out 94 ms 17064 KB Time limit exceeded (wall clock)
15 Execution timed out 90 ms 19176 KB Time limit exceeded (wall clock)
16 Execution timed out 66 ms 22692 KB Time limit exceeded (wall clock)
17 Execution timed out 69 ms 21960 KB Time limit exceeded (wall clock)