oj.uz

Submission #747042

# Submission time Handle Problem Language Result Execution time Memory
747042 2023-05-23T13:10:25 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
75 / 100
 8000 ms 40068 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]);
		}	
	}
	map<pair<int, int>, int> done;
	while(q--) {
		int i, j; scanf("%d%d", &i, &j);
		int ans = 0;
		if (done.count({i,j})) { ans = done[{i,j}]; }
		else {
			for (int parent:color[i])
				ans += b[j].order_of_key(tout[parent]) - b[j].order_of_key(tin[parent]);
			done[{i,j}] = ans;
		}	
		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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   int i, j; scanf("%d%d", &i, &j);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 6 ms 7520 KB Output is correct
3 Correct 9 ms 7504 KB Output is correct
4 Correct 13 ms 7572 KB Output is correct
5 Correct 20 ms 7628 KB Output is correct
6 Correct 29 ms 7652 KB Output is correct
7 Correct 41 ms 7848 KB Output is correct
8 Correct 38 ms 7908 KB Output is correct
9 Correct 59 ms 8428 KB Output is correct
10 Correct 107 ms 8936 KB Output is correct
11 Correct 149 ms 9464 KB Output is correct
12 Correct 135 ms 10320 KB Output is correct
13 Correct 259 ms 10680 KB Output is correct
14 Correct 381 ms 11080 KB Output is correct
15 Correct 386 ms 13396 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1850 ms 16668 KB Output is correct
2 Correct 2189 ms 16824 KB Output is correct
3 Correct 3221 ms 21080 KB Output is correct
4 Correct 370 ms 11980 KB Output is correct
5 Correct 450 ms 13952 KB Output is correct
6 Correct 577 ms 14632 KB Output is correct
7 Correct 792 ms 15936 KB Output is correct
8 Correct 1580 ms 23164 KB Output is correct
9 Correct 2974 ms 30484 KB Output is correct
10 Correct 5171 ms 36424 KB Output is correct
11 Correct 6222 ms 38584 KB Output is correct
12 Correct 7662 ms 30336 KB Output is correct
13 Execution timed out 8090 ms 32868 KB Time limit exceeded
14 Execution timed out 8020 ms 32336 KB Time limit exceeded
15 Execution timed out 8071 ms 35468 KB Time limit exceeded
16 Execution timed out 8090 ms 40068 KB Time limit exceeded
17 Execution timed out 8022 ms 39924 KB Time limit exceeded