oj.uz

Submission #781003

# Submission time Handle Problem Language Result Execution time Memory
781003 2023-07-12T15:32:21 Z Blagoj Stations (IOI20_stations) C++17
100 / 100
 842 ms 916 KB 
#include <bits/stdc++.h>
#include "stations.h"

using namespace std;

vector<int> g[1005], labels;
int in[1005], out[1005], timer = 0;

void dfs(int n, int p, bool even) {
	if (even) labels[n] = ++timer;
	for (auto x : g[n]) if (x != p) dfs(x, n, !even);
	if (!even) labels[n] = ++timer;
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	labels.resize(n, 0);
	for (int i = 0; i < n; i++) g[i].clear();
	timer = 0;
	for (int i = 0; i < u.size(); i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0, -1, 1);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.back() < s) reverse(c.begin(), c.end());
	for (auto x : c) if (min(x, s) <= t && t <= max(x, s)) return x;
	return c.back();
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 720 KB Output is correct
2 Correct 307 ms 780 KB Output is correct
3 Correct 711 ms 532 KB Output is correct
4 Correct 460 ms 524 KB Output is correct
5 Correct 554 ms 532 KB Output is correct
6 Correct 428 ms 644 KB Output is correct
7 Correct 402 ms 528 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 604 KB Output is correct
2 Correct 329 ms 544 KB Output is correct
3 Correct 747 ms 536 KB Output is correct
4 Correct 540 ms 588 KB Output is correct
5 Correct 364 ms 608 KB Output is correct
6 Correct 383 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 728 KB Output is correct
2 Correct 447 ms 672 KB Output is correct
3 Correct 842 ms 608 KB Output is correct
4 Correct 578 ms 532 KB Output is correct
5 Correct 444 ms 528 KB Output is correct
6 Correct 338 ms 740 KB Output is correct
7 Correct 425 ms 544 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 3 ms 540 KB Output is correct
10 Correct 1 ms 556 KB Output is correct
11 Correct 513 ms 600 KB Output is correct
12 Correct 358 ms 772 KB Output is correct
13 Correct 352 ms 916 KB Output is correct
14 Correct 351 ms 720 KB Output is correct
15 Correct 50 ms 484 KB Output is correct
16 Correct 37 ms 620 KB Output is correct
17 Correct 75 ms 608 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 528 KB Output is correct
2 Correct 600 ms 560 KB Output is correct
3 Correct 398 ms 416 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 454 ms 676 KB Output is correct
8 Correct 705 ms 532 KB Output is correct
9 Correct 557 ms 540 KB Output is correct
10 Correct 633 ms 592 KB Output is correct
11 Correct 6 ms 680 KB Output is correct
12 Correct 3 ms 500 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 417 ms 532 KB Output is correct
17 Correct 427 ms 528 KB Output is correct
18 Correct 438 ms 532 KB Output is correct
19 Correct 308 ms 608 KB Output is correct
20 Correct 362 ms 528 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 672 KB Output is correct
2 Correct 489 ms 528 KB Output is correct
3 Correct 746 ms 528 KB Output is correct
4 Correct 580 ms 536 KB Output is correct
5 Correct 496 ms 536 KB Output is correct
6 Correct 360 ms 544 KB Output is correct
7 Correct 369 ms 536 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 311 ms 528 KB Output is correct
12 Correct 362 ms 544 KB Output is correct
13 Correct 785 ms 536 KB Output is correct
14 Correct 537 ms 420 KB Output is correct
15 Correct 374 ms 540 KB Output is correct
16 Correct 369 ms 548 KB Output is correct
17 Correct 511 ms 532 KB Output is correct
18 Correct 414 ms 656 KB Output is correct
19 Correct 323 ms 764 KB Output is correct
20 Correct 330 ms 676 KB Output is correct
21 Correct 48 ms 560 KB Output is correct
22 Correct 59 ms 572 KB Output is correct
23 Correct 71 ms 712 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 3 ms 480 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 2 ms 500 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 326 ms 428 KB Output is correct
30 Correct 477 ms 420 KB Output is correct
31 Correct 424 ms 420 KB Output is correct
32 Correct 400 ms 420 KB Output is correct
33 Correct 462 ms 532 KB Output is correct
34 Correct 284 ms 656 KB Output is correct
35 Correct 280 ms 676 KB Output is correct
36 Correct 346 ms 768 KB Output is correct
37 Correct 383 ms 636 KB Output is correct
38 Correct 362 ms 544 KB Output is correct
39 Correct 368 ms 768 KB Output is correct
40 Correct 322 ms 636 KB Output is correct
41 Correct 318 ms 532 KB Output is correct
42 Correct 52 ms 676 KB Output is correct
43 Correct 71 ms 600 KB Output is correct
44 Correct 89 ms 544 KB Output is correct
45 Correct 105 ms 544 KB Output is correct
46 Correct 277 ms 532 KB Output is correct
47 Correct 228 ms 544 KB Output is correct
48 Correct 55 ms 728 KB Output is correct
49 Correct 47 ms 716 KB Output is correct