oj.uz

Submission #746555

# Submission time Handle Problem Language Result Execution time Memory
746555 2023-05-22T18:13:09 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
60 / 100
 8000 ms 32108 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() {
	scanf("%d%d%d", &n, &r, &q);
	int l; scanf("%d", &l); color[l].pb(0);
	for (int i=1, s, e;i<=n-1;i++) {
		scanf("%d%d", &s, &e);
		s--;
		adj[s].pb(i), adj[i].pb(s);
		color[e].pb(i);
	}
	dfs();
	for (int i = 0; i < R; i++) {
		for (int j: color[i]) {
			b[i].insert(tin[j]);
		}	
	}
	while(q--) {
		int i, j; scanf("%d%d", &i, &j);
		int ans = 0;
		for (int parent:color[i])
			ans += b[j].order_of_key(tout[parent]) - b[j].order_of_key(tin[parent]);
		printf("%d\n", ans);
		fflush(stdout);
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf("%d%d%d", &n, &r, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  int l; scanf("%d", &l); color[l].pb(0);
      |         ~~~~~^~~~~~~~~~
regions.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   int i, j; scanf("%d%d", &i, &j);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7504 KB Output is correct
2 Correct 5 ms 7504 KB Output is correct
3 Correct 8 ms 7504 KB Output is correct
4 Correct 11 ms 7504 KB Output is correct
5 Correct 14 ms 7504 KB Output is correct
6 Correct 19 ms 7540 KB Output is correct
7 Correct 41 ms 7632 KB Output is correct
8 Correct 32 ms 7632 KB Output is correct
9 Correct 57 ms 8144 KB Output is correct
10 Correct 92 ms 8488 KB Output is correct
11 Correct 164 ms 8912 KB Output is correct
12 Correct 184 ms 9424 KB Output is correct
13 Correct 239 ms 9680 KB Output is correct
14 Correct 391 ms 10320 KB Output is correct
15 Correct 416 ms 12432 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8020 ms 14824 KB Time limit exceeded
2 Execution timed out 8085 ms 14932 KB Time limit exceeded
3 Execution timed out 8074 ms 16796 KB Time limit exceeded
4 Correct 328 ms 10448 KB Output is correct
5 Correct 439 ms 11728 KB Output is correct
6 Correct 1607 ms 12500 KB Output is correct
7 Correct 2078 ms 14152 KB Output is correct
8 Correct 1520 ms 18956 KB Output is correct
9 Correct 2790 ms 22172 KB Output is correct
10 Correct 5316 ms 26408 KB Output is correct
11 Correct 6099 ms 26696 KB Output is correct
12 Correct 7740 ms 25164 KB Output is correct
13 Execution timed out 8063 ms 25632 KB Time limit exceeded
14 Execution timed out 8041 ms 26416 KB Time limit exceeded
15 Execution timed out 8029 ms 28448 KB Time limit exceeded
16 Execution timed out 8058 ms 32108 KB Time limit exceeded
17 Execution timed out 8026 ms 31304 KB Time limit exceeded