oj.uz

Submission #720225

# Submission time Handle Problem Language Result Execution time Memory
720225 2023-04-07T16:45:23 Z thimote75 Stations (IOI20_stations) C++14
100 / 100
 935 ms 752 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>
#define graph vector<idata>

graph roads;

int component = 0;
void dfs (int node, int parent, bool type, idata &labels) {
	if (type) {
		labels[node] = component;
		component ++;
	}

	for (int next : roads[node]) if (next != parent)
		dfs(next, node, !type, labels);
	
	if (!type) {
		labels[node] = component;
		component ++;
	}
}

idata label(int n, int k, idata u, idata v) {
	component = 0;
	roads.clear();
	roads.resize(n);
	
	for (int i = 0; i + 1 < n; i ++) {
		roads[u[i]].push_back(v[i]);
		roads[v[i]].push_back(u[i]);
	}

	idata labels(n);
	dfs(0, -1, true, labels);

	return labels;
}

int find_next_station(int s, int t, idata c) {
	bool is_root = s == 0;
	bool is_revr = c[0] < s;

	if (is_revr) {
		for (int i = 0; i < c.size(); i ++)
			c[i] = - c[i];
		s = -s;
		t = -t;
	}
	sort(c.begin(), c.end());

	int size = c.size();
	if (!is_root) size --;

	int result = c[c.size() - 1];
	for (int h = 0; h < size; h ++) {
		if (s < t && t <= c[h]) {
			result = c[h];
			break ;
		}
	}

	return is_revr ? -result : result;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 548 KB Output is correct
2 Correct 419 ms 640 KB Output is correct
3 Correct 799 ms 508 KB Output is correct
4 Correct 677 ms 420 KB Output is correct
5 Correct 530 ms 508 KB Output is correct
6 Correct 469 ms 548 KB Output is correct
7 Correct 463 ms 548 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 1 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 640 KB Output is correct
2 Correct 526 ms 496 KB Output is correct
3 Correct 804 ms 436 KB Output is correct
4 Correct 746 ms 420 KB Output is correct
5 Correct 556 ms 504 KB Output is correct
6 Correct 382 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 640 KB Output is correct
2 Correct 446 ms 636 KB Output is correct
3 Correct 857 ms 484 KB Output is correct
4 Correct 593 ms 416 KB Output is correct
5 Correct 598 ms 416 KB Output is correct
6 Correct 518 ms 636 KB Output is correct
7 Correct 443 ms 544 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 5 ms 496 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 630 ms 504 KB Output is correct
12 Correct 471 ms 716 KB Output is correct
13 Correct 505 ms 736 KB Output is correct
14 Correct 424 ms 504 KB Output is correct
15 Correct 48 ms 500 KB Output is correct
16 Correct 63 ms 544 KB Output is correct
17 Correct 118 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 512 KB Output is correct
2 Correct 588 ms 420 KB Output is correct
3 Correct 618 ms 504 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 628 ms 444 KB Output is correct
8 Correct 935 ms 512 KB Output is correct
9 Correct 704 ms 416 KB Output is correct
10 Correct 529 ms 532 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 4 ms 500 KB Output is correct
14 Correct 4 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 531 ms 416 KB Output is correct
17 Correct 530 ms 416 KB Output is correct
18 Correct 512 ms 420 KB Output is correct
19 Correct 531 ms 508 KB Output is correct
20 Correct 520 ms 500 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 628 KB Output is correct
2 Correct 422 ms 676 KB Output is correct
3 Correct 862 ms 416 KB Output is correct
4 Correct 642 ms 432 KB Output is correct
5 Correct 577 ms 416 KB Output is correct
6 Correct 448 ms 616 KB Output is correct
7 Correct 429 ms 548 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 496 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 439 ms 504 KB Output is correct
12 Correct 493 ms 548 KB Output is correct
13 Correct 862 ms 508 KB Output is correct
14 Correct 604 ms 416 KB Output is correct
15 Correct 618 ms 420 KB Output is correct
16 Correct 474 ms 548 KB Output is correct
17 Correct 619 ms 512 KB Output is correct
18 Correct 473 ms 668 KB Output is correct
19 Correct 476 ms 668 KB Output is correct
20 Correct 439 ms 536 KB Output is correct
21 Correct 45 ms 460 KB Output is correct
22 Correct 68 ms 508 KB Output is correct
23 Correct 102 ms 508 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 4 ms 504 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 4 ms 500 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 494 ms 520 KB Output is correct
30 Correct 502 ms 504 KB Output is correct
31 Correct 475 ms 416 KB Output is correct
32 Correct 543 ms 420 KB Output is correct
33 Correct 536 ms 508 KB Output is correct
34 Correct 307 ms 632 KB Output is correct
35 Correct 449 ms 548 KB Output is correct
36 Correct 496 ms 752 KB Output is correct
37 Correct 404 ms 624 KB Output is correct
38 Correct 401 ms 636 KB Output is correct
39 Correct 479 ms 668 KB Output is correct
40 Correct 475 ms 548 KB Output is correct
41 Correct 470 ms 668 KB Output is correct
42 Correct 71 ms 572 KB Output is correct
43 Correct 111 ms 568 KB Output is correct
44 Correct 136 ms 544 KB Output is correct
45 Correct 133 ms 544 KB Output is correct
46 Correct 325 ms 544 KB Output is correct
47 Correct 324 ms 548 KB Output is correct
48 Correct 48 ms 572 KB Output is correct
49 Correct 54 ms 660 KB Output is correct