oj.uz

Submission #615906

# Submission time Handle Problem Language Result Execution time Memory
615906 2022-07-31T14:05:10 Z fvogel499 Stations (IOI20_stations) C++17
100 / 100
 904 ms 47784 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

vector<int> graph [1000*1000];
vector<int> assign;

int curT;
void dfs(int x, int p = -1, int h = 0) {
	if (h%2 == 0) {
		assign[x] = curT;
		curT++;
	}
	for (int y : graph[x]) if (y != p) {
		dfs(y, x, h+1);
	}
	if (h%2 == 1) {
		assign[x] = curT;
		curT++;
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for (int i = 0; i < n; i++) {
		graph[i].clear();
	}
	for (int i = 0; i < n-1; i++) {
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	assign = vector<int>(n, -1);
	curT = 0;
	dfs(0);
	return assign;
}

int find_next_station(int curL, int tarL, std::vector<int> adj) {
	sort(adj.begin(), adj.end());
	if (curL == 0) { // the root
		for (int i : adj) {
			if (tarL <= i) {
				return i;
			}
		}
		assert(false);
		return -1;
	}
	vector<pair<int, pair<int, int>>> ints;
	int parent;
	if (adj[0] > curL) {
		parent = adj.back();
		for (int i = 0; i < adj.size()-1; i++) {
			int bef = curL+1;
			if (i) bef = adj[i-1]+1;
			ints.push_back({adj[i], {bef, adj[i]}});
		}
	}
	else {
		parent = adj[0];
		assert(adj.back() < curL);
		for (int i = 1; i < adj.size(); i++) {
			int aft = curL-1;
			if (i+1 < adj.size()) aft = adj[i+1]-1;
			ints.push_back({adj[i], {adj[i], aft}});
		}
	}
	for (auto i : ints) {
		if (i.second.first <= tarL && tarL <= i.second.second) {
			return i.first;
		}
	}
	return parent;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 47672 KB Output is correct
2 Correct 484 ms 47780 KB Output is correct
3 Correct 754 ms 47520 KB Output is correct
4 Correct 657 ms 47520 KB Output is correct
5 Correct 666 ms 47544 KB Output is correct
6 Correct 505 ms 47668 KB Output is correct
7 Correct 450 ms 47648 KB Output is correct
8 Correct 31 ms 47428 KB Output is correct
9 Correct 34 ms 47508 KB Output is correct
10 Correct 26 ms 47412 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 47536 KB Output is correct
2 Correct 541 ms 47540 KB Output is correct
3 Correct 854 ms 47520 KB Output is correct
4 Correct 726 ms 47528 KB Output is correct
5 Correct 537 ms 47524 KB Output is correct
6 Correct 458 ms 47540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 47652 KB Output is correct
2 Correct 484 ms 47668 KB Output is correct
3 Correct 728 ms 47444 KB Output is correct
4 Correct 639 ms 47452 KB Output is correct
5 Correct 612 ms 47584 KB Output is correct
6 Correct 515 ms 47672 KB Output is correct
7 Correct 490 ms 47548 KB Output is correct
8 Correct 27 ms 47648 KB Output is correct
9 Correct 32 ms 47500 KB Output is correct
10 Correct 27 ms 47624 KB Output is correct
11 Correct 536 ms 47520 KB Output is correct
12 Correct 421 ms 47692 KB Output is correct
13 Correct 507 ms 47656 KB Output is correct
14 Correct 475 ms 47524 KB Output is correct
15 Correct 88 ms 47548 KB Output is correct
16 Correct 116 ms 47544 KB Output is correct
17 Correct 136 ms 47584 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 47520 KB Output is correct
2 Correct 601 ms 47520 KB Output is correct
3 Correct 646 ms 47544 KB Output is correct
4 Correct 27 ms 47612 KB Output is correct
5 Correct 34 ms 47556 KB Output is correct
6 Correct 28 ms 47572 KB Output is correct
7 Correct 637 ms 47524 KB Output is correct
8 Correct 800 ms 47520 KB Output is correct
9 Correct 653 ms 47516 KB Output is correct
10 Correct 628 ms 47520 KB Output is correct
11 Correct 28 ms 47556 KB Output is correct
12 Correct 31 ms 47448 KB Output is correct
13 Correct 27 ms 47600 KB Output is correct
14 Correct 27 ms 47480 KB Output is correct
15 Correct 26 ms 47520 KB Output is correct
16 Correct 546 ms 47612 KB Output is correct
17 Correct 597 ms 47520 KB Output is correct
18 Correct 510 ms 47524 KB Output is correct
19 Correct 575 ms 47524 KB Output is correct
20 Correct 488 ms 47520 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 47652 KB Output is correct
2 Correct 390 ms 47548 KB Output is correct
3 Correct 901 ms 47524 KB Output is correct
4 Correct 669 ms 47548 KB Output is correct
5 Correct 546 ms 47520 KB Output is correct
6 Correct 406 ms 47652 KB Output is correct
7 Correct 439 ms 47652 KB Output is correct
8 Correct 27 ms 47644 KB Output is correct
9 Correct 32 ms 47636 KB Output is correct
10 Correct 27 ms 47624 KB Output is correct
11 Correct 481 ms 47544 KB Output is correct
12 Correct 521 ms 47444 KB Output is correct
13 Correct 803 ms 47520 KB Output is correct
14 Correct 673 ms 47544 KB Output is correct
15 Correct 551 ms 47676 KB Output is correct
16 Correct 453 ms 47580 KB Output is correct
17 Correct 622 ms 47460 KB Output is correct
18 Correct 490 ms 47664 KB Output is correct
19 Correct 480 ms 47668 KB Output is correct
20 Correct 515 ms 47536 KB Output is correct
21 Correct 78 ms 47636 KB Output is correct
22 Correct 113 ms 47592 KB Output is correct
23 Correct 114 ms 47524 KB Output is correct
24 Correct 30 ms 47624 KB Output is correct
25 Correct 30 ms 47524 KB Output is correct
26 Correct 30 ms 47624 KB Output is correct
27 Correct 27 ms 47644 KB Output is correct
28 Correct 27 ms 47476 KB Output is correct
29 Correct 475 ms 47544 KB Output is correct
30 Correct 494 ms 47544 KB Output is correct
31 Correct 545 ms 47424 KB Output is correct
32 Correct 495 ms 47528 KB Output is correct
33 Correct 553 ms 47520 KB Output is correct
34 Correct 304 ms 47548 KB Output is correct
35 Correct 449 ms 47652 KB Output is correct
36 Correct 410 ms 47652 KB Output is correct
37 Correct 420 ms 47784 KB Output is correct
38 Correct 474 ms 47780 KB Output is correct
39 Correct 395 ms 47680 KB Output is correct
40 Correct 458 ms 47556 KB Output is correct
41 Correct 479 ms 47684 KB Output is correct
42 Correct 91 ms 47524 KB Output is correct
43 Correct 134 ms 47640 KB Output is correct
44 Correct 133 ms 47628 KB Output is correct
45 Correct 146 ms 47592 KB Output is correct
46 Correct 337 ms 47596 KB Output is correct
47 Correct 346 ms 47608 KB Output is correct
48 Correct 93 ms 47708 KB Output is correct
49 Correct 72 ms 47712 KB Output is correct