oj.uz

Submission #785015

# Submission time Handle Problem Language Result Execution time Memory
785015 2023-07-16T22:59:11 Z zsombor Stations (IOI20_stations) C++17
100 / 100
 801 ms 724 KB 
#include <iostream>
#include <vector>
#include "stations.h"
using namespace std;

vector <vector <int>> g;
vector <int> sz;
vector <int> lbl;

void dfs1(int x) {
	sz[x] = 1;
	for (int i : g[x]) {
		if (sz[i]) continue;
		dfs1(i);
		sz[x] += sz[i];
	}
}

void dfs2(int x, int l, int r, bool b) {
	if (b) { lbl[x] = l; l++; }
	else { lbl[x] = r; r--; }
	for (int i : g[x]) {
		if (lbl[i] > -1) continue;
		dfs2(i, l, l + sz[i] - 1, !b);
		l += sz[i];
	}
}

vector <int> label(int n, int k, vector <int> u, vector <int> v) {
	g.assign(n, {});
	sz.assign(n, 0);
	lbl.assign(n, -1);
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs1(0);
	dfs2(0, 0, n - 1, true);
	return lbl;
}

int find_next_station(int s, int t, vector <int> c) {
	if (c.size() == 1) return c[0];
	if (s == 0) {
		for (int i = 0; i < c.size(); i++) if (t <= c[i]) return c[i];
	}
	if (s < c[0]) {
		if (t < s || c[c.size() - 2] < t) return c.back();
		for (int i = 0; i < c.size() - 1; i++) if (t <= c[i]) return c[i];
	}
	if (c.back() < s) {
		if (t < c[1] || s < t) return c[0];
		for (int i = c.size() - 1; i > 0; i--) if (t >= c[i]) return c[i];
	}
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 652 KB Output is correct
2 Correct 340 ms 636 KB Output is correct
3 Correct 697 ms 544 KB Output is correct
4 Correct 541 ms 496 KB Output is correct
5 Correct 478 ms 492 KB Output is correct
6 Correct 346 ms 624 KB Output is correct
7 Correct 358 ms 544 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 632 KB Output is correct
2 Correct 419 ms 544 KB Output is correct
3 Correct 734 ms 508 KB Output is correct
4 Correct 436 ms 500 KB Output is correct
5 Correct 466 ms 512 KB Output is correct
6 Correct 405 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 676 KB Output is correct
2 Correct 315 ms 640 KB Output is correct
3 Correct 696 ms 508 KB Output is correct
4 Correct 511 ms 416 KB Output is correct
5 Correct 430 ms 508 KB Output is correct
6 Correct 288 ms 672 KB Output is correct
7 Correct 452 ms 544 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 444 ms 416 KB Output is correct
12 Correct 322 ms 720 KB Output is correct
13 Correct 445 ms 712 KB Output is correct
14 Correct 378 ms 544 KB Output is correct
15 Correct 47 ms 492 KB Output is correct
16 Correct 55 ms 616 KB Output is correct
17 Correct 76 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 504 KB Output is correct
2 Correct 511 ms 420 KB Output is correct
3 Correct 477 ms 508 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 474 ms 416 KB Output is correct
8 Correct 769 ms 512 KB Output is correct
9 Correct 617 ms 420 KB Output is correct
10 Correct 472 ms 500 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 3 ms 488 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 1 ms 500 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 481 ms 512 KB Output is correct
17 Correct 400 ms 416 KB Output is correct
18 Correct 380 ms 464 KB Output is correct
19 Correct 416 ms 420 KB Output is correct
20 Correct 431 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 636 KB Output is correct
2 Correct 331 ms 652 KB Output is correct
3 Correct 744 ms 516 KB Output is correct
4 Correct 605 ms 500 KB Output is correct
5 Correct 454 ms 588 KB Output is correct
6 Correct 321 ms 548 KB Output is correct
7 Correct 282 ms 544 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 496 KB Output is correct
11 Correct 311 ms 544 KB Output is correct
12 Correct 355 ms 544 KB Output is correct
13 Correct 801 ms 544 KB Output is correct
14 Correct 550 ms 500 KB Output is correct
15 Correct 484 ms 416 KB Output is correct
16 Correct 459 ms 544 KB Output is correct
17 Correct 561 ms 416 KB Output is correct
18 Correct 367 ms 580 KB Output is correct
19 Correct 368 ms 628 KB Output is correct
20 Correct 309 ms 508 KB Output is correct
21 Correct 55 ms 420 KB Output is correct
22 Correct 50 ms 572 KB Output is correct
23 Correct 86 ms 548 KB Output is correct
24 Correct 5 ms 500 KB Output is correct
25 Correct 4 ms 500 KB Output is correct
26 Correct 4 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 478 ms 420 KB Output is correct
30 Correct 478 ms 416 KB Output is correct
31 Correct 383 ms 416 KB Output is correct
32 Correct 343 ms 420 KB Output is correct
33 Correct 371 ms 544 KB Output is correct
34 Correct 234 ms 628 KB Output is correct
35 Correct 264 ms 544 KB Output is correct
36 Correct 427 ms 688 KB Output is correct
37 Correct 422 ms 624 KB Output is correct
38 Correct 400 ms 724 KB Output is correct
39 Correct 409 ms 624 KB Output is correct
40 Correct 339 ms 624 KB Output is correct
41 Correct 307 ms 588 KB Output is correct
42 Correct 45 ms 604 KB Output is correct
43 Correct 68 ms 596 KB Output is correct
44 Correct 99 ms 544 KB Output is correct
45 Correct 138 ms 600 KB Output is correct
46 Correct 171 ms 544 KB Output is correct
47 Correct 285 ms 544 KB Output is correct
48 Correct 45 ms 704 KB Output is correct
49 Correct 42 ms 700 KB Output is correct