oj.uz

답안 #772529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772529 2023-07-04T07:53:05 Z SanguineChameleon 기지국 (IOI20_stations) C++17
100 / 100
 905 ms 804 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 20;
vector<int> adj[maxn];
int tin[maxn];
int tout[maxn];
int depth[maxn];
int dfs_t;

void dfs(int u, int p) {
	tin[u] = ++dfs_t;
	for (auto v: adj[u]) {
		if (v != p) {
			depth[v] = depth[u] + 1;
			dfs(v, u);
		}
	}
	tout[u] = ++dfs_t;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs_t = -1;
	dfs(0, -1);
	vector<pair<int, int>> order(n);
	for (int i = 0; i < n; i++) {
		order[i] = make_pair(depth[i] & 1 ? tout[i] : tin[i], i);
	}
	sort(order.begin(), order.end());
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[order[i].second] = i;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(c.begin(), c.end());
	if (s < c[0]) {
		for (int i = 0; i < (int)c.size() - 1; i++) {
			if ((i ? c[i - 1] : s) < t && t <= c[i]) {
				return c[i];
			}
		}
		return c.back();
	}
	else {
		for (int i = 1; i < (int)c.size(); i++) {
			if (c[i] <= t && t < (i < (int)c.size() - 1 ? c[i + 1] : s)) {
				return c[i];
			}
		}
		return c[0];
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 548 KB Output is correct
2 Correct 367 ms 668 KB Output is correct
3 Correct 668 ms 416 KB Output is correct
4 Correct 513 ms 532 KB Output is correct
5 Correct 465 ms 544 KB Output is correct
6 Correct 412 ms 688 KB Output is correct
7 Correct 312 ms 548 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 628 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 398 ms 544 KB Output is correct
2 Correct 411 ms 544 KB Output is correct
3 Correct 905 ms 544 KB Output is correct
4 Correct 480 ms 528 KB Output is correct
5 Correct 547 ms 548 KB Output is correct
6 Correct 334 ms 536 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 469 ms 656 KB Output is correct
2 Correct 354 ms 548 KB Output is correct
3 Correct 729 ms 568 KB Output is correct
4 Correct 432 ms 544 KB Output is correct
5 Correct 516 ms 532 KB Output is correct
6 Correct 363 ms 548 KB Output is correct
7 Correct 389 ms 668 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 562 ms 532 KB Output is correct
12 Correct 377 ms 656 KB Output is correct
13 Correct 324 ms 772 KB Output is correct
14 Correct 357 ms 548 KB Output is correct
15 Correct 32 ms 620 KB Output is correct
16 Correct 54 ms 548 KB Output is correct
17 Correct 78 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 713 ms 596 KB Output is correct
2 Correct 494 ms 536 KB Output is correct
3 Correct 439 ms 532 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 0 ms 488 KB Output is correct
7 Correct 475 ms 536 KB Output is correct
8 Correct 738 ms 548 KB Output is correct
9 Correct 590 ms 536 KB Output is correct
10 Correct 473 ms 548 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 1 ms 628 KB Output is correct
16 Correct 414 ms 548 KB Output is correct
17 Correct 433 ms 420 KB Output is correct
18 Correct 344 ms 544 KB Output is correct
19 Correct 363 ms 660 KB Output is correct
20 Correct 383 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 407 ms 664 KB Output is correct
2 Correct 327 ms 656 KB Output is correct
3 Correct 702 ms 544 KB Output is correct
4 Correct 518 ms 548 KB Output is correct
5 Correct 423 ms 420 KB Output is correct
6 Correct 386 ms 544 KB Output is correct
7 Correct 320 ms 548 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 435 ms 532 KB Output is correct
12 Correct 469 ms 536 KB Output is correct
13 Correct 677 ms 532 KB Output is correct
14 Correct 525 ms 548 KB Output is correct
15 Correct 356 ms 544 KB Output is correct
16 Correct 391 ms 536 KB Output is correct
17 Correct 418 ms 416 KB Output is correct
18 Correct 366 ms 544 KB Output is correct
19 Correct 370 ms 804 KB Output is correct
20 Correct 359 ms 544 KB Output is correct
21 Correct 29 ms 616 KB Output is correct
22 Correct 73 ms 600 KB Output is correct
23 Correct 84 ms 676 KB Output is correct
24 Correct 4 ms 620 KB Output is correct
25 Correct 2 ms 616 KB Output is correct
26 Correct 3 ms 620 KB Output is correct
27 Correct 2 ms 488 KB Output is correct
28 Correct 1 ms 628 KB Output is correct
29 Correct 430 ms 544 KB Output is correct
30 Correct 381 ms 544 KB Output is correct
31 Correct 439 ms 420 KB Output is correct
32 Correct 414 ms 676 KB Output is correct
33 Correct 434 ms 544 KB Output is correct
34 Correct 221 ms 532 KB Output is correct
35 Correct 332 ms 660 KB Output is correct
36 Correct 440 ms 764 KB Output is correct
37 Correct 407 ms 704 KB Output is correct
38 Correct 368 ms 660 KB Output is correct
39 Correct 328 ms 648 KB Output is correct
40 Correct 400 ms 652 KB Output is correct
41 Correct 387 ms 748 KB Output is correct
42 Correct 46 ms 572 KB Output is correct
43 Correct 104 ms 640 KB Output is correct
44 Correct 97 ms 544 KB Output is correct
45 Correct 112 ms 540 KB Output is correct
46 Correct 234 ms 548 KB Output is correct
47 Correct 283 ms 536 KB Output is correct
48 Correct 53 ms 728 KB Output is correct
49 Correct 39 ms 764 KB Output is correct