oj.uz

답안 #747051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747051 2023-05-23T13:48:47 Z AverageAmogusEnjoyer Regions (IOI09_regions) C++17
85 / 100
 8000 ms 45004 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];
vector<array<int, 2>> time_in_node[R];
indexed_set<int> time_in[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]) {
			time_in[i].insert(tin[j]);
			time_in_node[i].pb({tin[j],j});
		}
		sort(all(time_in_node[i]));	
	}
	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 {
			int sz = time_in_node[i].size(), k = 0;
			while(k < sz) {
				int curr_node = time_in_node[i][k][1];
				array<int,2> l = {tout[curr_node],0};
				int curr = time_in[j].order_of_key(tout[curr_node]) - time_in[j].order_of_key(tin[curr_node]);
				assert(curr>=0);
				ans += curr;
				if (curr == 0) {
					k = (upper_bound(all(time_in_node[i]),l) - time_in_node[i].begin());
				}
				else 
					k++;
			}
			done[{i,j}] = ans;
		}	
		printf("%d\n", ans);
		fflush(stdout);
	}
}

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8144 KB Output is correct
2 Correct 5 ms 8132 KB Output is correct
3 Correct 8 ms 8144 KB Output is correct
4 Correct 14 ms 8168 KB Output is correct
5 Correct 15 ms 8212 KB Output is correct
6 Correct 20 ms 8288 KB Output is correct
7 Correct 41 ms 8412 KB Output is correct
8 Correct 42 ms 8504 KB Output is correct
9 Correct 64 ms 8992 KB Output is correct
10 Correct 120 ms 9612 KB Output is correct
11 Correct 167 ms 10196 KB Output is correct
12 Correct 189 ms 10972 KB Output is correct
13 Correct 304 ms 11432 KB Output is correct
14 Correct 421 ms 12012 KB Output is correct
15 Correct 319 ms 14480 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1533 ms 17956 KB Output is correct
2 Correct 2190 ms 18104 KB Output is correct
3 Correct 2762 ms 22296 KB Output is correct
4 Correct 348 ms 12888 KB Output is correct
5 Correct 356 ms 14968 KB Output is correct
6 Correct 507 ms 15744 KB Output is correct
7 Correct 1000 ms 16876 KB Output is correct
8 Correct 1448 ms 24884 KB Output is correct
9 Correct 3032 ms 33132 KB Output is correct
10 Correct 5773 ms 39052 KB Output is correct
11 Execution timed out 8003 ms 41544 KB Time limit exceeded
12 Correct 3995 ms 32960 KB Output is correct
13 Correct 4304 ms 35676 KB Output is correct
14 Correct 6044 ms 37876 KB Output is correct
15 Correct 7125 ms 42716 KB Output is correct
16 Execution timed out 8061 ms 44088 KB Time limit exceeded
17 Execution timed out 8077 ms 45004 KB Time limit exceeded