oj.uz

답안 #996747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
996747 2024-06-11T06:46:44 Z phoenix 기지국 (IOI20_stations) C++17
100 / 100
 663 ms 1044 KB 
#include "stations.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

using namespace std;

const int N = 1010;

int T;
int tin[N];
int tout[N];
vector<int> g[N];

void precalc(int s, int p) {
	tin[s] = T++;
	for (int to : g[s]) if (to != p)
		precalc(to, s);
	tout[s] = T++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	T = 0;
	for (int i = 0; i < n; i++) {
		g[i].clear();
	}
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}	
	vector<int> labels(n);
	precalc(0, 0);
	for (int i = 0; i < n; i++)
		if (tin[i] & 1) 
			labels[i] = tout[i];
		else 
			labels[i] = tin[i];
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int x, int y) {
		return labels[x] < labels[y];
	});	
	for (int i = 0; i < n; i++) 
		labels[ord[i]] = i;
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if ((int)c.size() == 1) 
		return c[0];
	int m = (int)c.size();
	sort(c.begin(), c.end());

	if (!s) {
		int prev = s;
		for (int i = 0; i < m; i++) {
			int l = prev + 1; 
			int r = c[i];
			prev = c[i];
			if (l <= t && t <= r)
				return c[i];
		}
	}

	if (s < c[0]) {
		int prev = s + 1;
		for (int i = 0; i < m - 1; i++) {
			int l = prev; 
			int r = c[i];
			prev = c[i] + 1;
			if (l <= t && t <= r)
				return c[i];
		}
		return c.back(	);
	} 
	int prev = s - 1;
	for (int i = m - 1; i >= 1; i--) {
		int l = c[i];
		int r = prev;
		prev = c[i] - 1;
		if (l <= t && t <= r) 
			return c[i];
	}
	return c[0];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 684 KB Output is correct
2 Correct 311 ms 684 KB Output is correct
3 Correct 593 ms 684 KB Output is correct
4 Correct 509 ms 684 KB Output is correct
5 Correct 410 ms 688 KB Output is correct
6 Correct 288 ms 684 KB Output is correct
7 Correct 315 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 684 KB Output is correct
2 Correct 380 ms 684 KB Output is correct
3 Correct 651 ms 684 KB Output is correct
4 Correct 457 ms 684 KB Output is correct
5 Correct 402 ms 684 KB Output is correct
6 Correct 325 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 417 ms 684 KB Output is correct
2 Correct 296 ms 684 KB Output is correct
3 Correct 658 ms 684 KB Output is correct
4 Correct 456 ms 684 KB Output is correct
5 Correct 377 ms 684 KB Output is correct
6 Correct 322 ms 684 KB Output is correct
7 Correct 317 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 393 ms 684 KB Output is correct
12 Correct 321 ms 932 KB Output is correct
13 Correct 307 ms 788 KB Output is correct
14 Correct 280 ms 684 KB Output is correct
15 Correct 31 ms 768 KB Output is correct
16 Correct 62 ms 684 KB Output is correct
17 Correct 56 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 626 ms 684 KB Output is correct
2 Correct 406 ms 684 KB Output is correct
3 Correct 380 ms 684 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 419 ms 684 KB Output is correct
8 Correct 607 ms 792 KB Output is correct
9 Correct 448 ms 684 KB Output is correct
10 Correct 407 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 1 ms 764 KB Output is correct
16 Correct 330 ms 792 KB Output is correct
17 Correct 342 ms 684 KB Output is correct
18 Correct 363 ms 684 KB Output is correct
19 Correct 336 ms 684 KB Output is correct
20 Correct 322 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 684 KB Output is correct
2 Correct 316 ms 684 KB Output is correct
3 Correct 663 ms 684 KB Output is correct
4 Correct 441 ms 680 KB Output is correct
5 Correct 390 ms 680 KB Output is correct
6 Correct 309 ms 684 KB Output is correct
7 Correct 326 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 308 ms 684 KB Output is correct
12 Correct 345 ms 684 KB Output is correct
13 Correct 572 ms 688 KB Output is correct
14 Correct 460 ms 684 KB Output is correct
15 Correct 372 ms 684 KB Output is correct
16 Correct 299 ms 684 KB Output is correct
17 Correct 401 ms 684 KB Output is correct
18 Correct 308 ms 944 KB Output is correct
19 Correct 304 ms 932 KB Output is correct
20 Correct 346 ms 684 KB Output is correct
21 Correct 29 ms 768 KB Output is correct
22 Correct 40 ms 712 KB Output is correct
23 Correct 56 ms 684 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 776 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 359 ms 684 KB Output is correct
30 Correct 364 ms 688 KB Output is correct
31 Correct 356 ms 684 KB Output is correct
32 Correct 368 ms 684 KB Output is correct
33 Correct 340 ms 684 KB Output is correct
34 Correct 237 ms 684 KB Output is correct
35 Correct 306 ms 788 KB Output is correct
36 Correct 325 ms 932 KB Output is correct
37 Correct 289 ms 1044 KB Output is correct
38 Correct 316 ms 932 KB Output is correct
39 Correct 319 ms 808 KB Output is correct
40 Correct 284 ms 792 KB Output is correct
41 Correct 293 ms 800 KB Output is correct
42 Correct 33 ms 704 KB Output is correct
43 Correct 57 ms 728 KB Output is correct
44 Correct 81 ms 684 KB Output is correct
45 Correct 110 ms 688 KB Output is correct
46 Correct 202 ms 684 KB Output is correct
47 Correct 221 ms 684 KB Output is correct
48 Correct 46 ms 848 KB Output is correct
49 Correct 32 ms 876 KB Output is correct