oj.uz

Submission #838473

# Submission time Handle Problem Language Result Execution time Memory
838473 2023-08-27T07:19:39 Z caganyanmaz Stations (IOI20_stations) C++17
100 / 100
 746 ms 1000 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 1010;
constexpr static int LOWER_BOUND = 0;
constexpr static int UPPER_BOUND = 1;
vector<int> labels, g[MXN];


int nxt;
void dfs(int node, int parent, int state)
{
	if (state == LOWER_BOUND)
		labels[node] = nxt++;
	for (int c : g[node])
		if (c != parent)
			dfs(c, node, state^1);
	if (state == UPPER_BOUND)
		labels[node] = nxt++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) 
{
	labels = vector<int>(n);
	for (int i = 0; i < n; i++)
		g[i].clear();
	for (int i = 0; i < n-1; i++)
	{
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	nxt = 0;
	dfs(0, 0, LOWER_BOUND);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) 
{
	debug(s, t, c);
	assert(!c.empty());
	int state;
	int lb, ub, parent;
	if (s > c[0]) // Upper Bound
	{
		state = UPPER_BOUND;
		parent = c[0];
		lb = parent; // Parent
		ub = s;
	}
	else
	{
		state = LOWER_BOUND;
		parent = c.back();
		lb = s;
		ub = parent; // Parent
	}
	if (t > ub || lb > t)
		return parent;
	auto it = lower_bound(c.begin(), c.end(), t);
	if (*it == t)
		return t;
	if (state == UPPER_BOUND)
		it--;
	return *it;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 804 KB Output is correct
2 Correct 315 ms 676 KB Output is correct
3 Correct 516 ms 416 KB Output is correct
4 Correct 561 ms 416 KB Output is correct
5 Correct 554 ms 524 KB Output is correct
6 Correct 421 ms 548 KB Output is correct
7 Correct 302 ms 548 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 552 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 548 KB Output is correct
2 Correct 458 ms 548 KB Output is correct
3 Correct 699 ms 420 KB Output is correct
4 Correct 569 ms 420 KB Output is correct
5 Correct 354 ms 420 KB Output is correct
6 Correct 289 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 704 KB Output is correct
2 Correct 322 ms 544 KB Output is correct
3 Correct 618 ms 416 KB Output is correct
4 Correct 450 ms 420 KB Output is correct
5 Correct 503 ms 416 KB Output is correct
6 Correct 371 ms 544 KB Output is correct
7 Correct 306 ms 548 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 415 ms 420 KB Output is correct
12 Correct 315 ms 548 KB Output is correct
13 Correct 308 ms 548 KB Output is correct
14 Correct 350 ms 544 KB Output is correct
15 Correct 44 ms 620 KB Output is correct
16 Correct 55 ms 600 KB Output is correct
17 Correct 79 ms 576 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 420 KB Output is correct
2 Correct 439 ms 420 KB Output is correct
3 Correct 490 ms 416 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 0 ms 496 KB Output is correct
7 Correct 398 ms 420 KB Output is correct
8 Correct 608 ms 420 KB Output is correct
9 Correct 449 ms 540 KB Output is correct
10 Correct 376 ms 420 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 1 ms 488 KB Output is correct
16 Correct 441 ms 540 KB Output is correct
17 Correct 372 ms 416 KB Output is correct
18 Correct 318 ms 420 KB Output is correct
19 Correct 342 ms 464 KB Output is correct
20 Correct 355 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 548 KB Output is correct
2 Correct 386 ms 548 KB Output is correct
3 Correct 544 ms 416 KB Output is correct
4 Correct 477 ms 416 KB Output is correct
5 Correct 398 ms 420 KB Output is correct
6 Correct 281 ms 544 KB Output is correct
7 Correct 264 ms 548 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 322 ms 548 KB Output is correct
12 Correct 502 ms 576 KB Output is correct
13 Correct 746 ms 416 KB Output is correct
14 Correct 458 ms 420 KB Output is correct
15 Correct 408 ms 416 KB Output is correct
16 Correct 340 ms 548 KB Output is correct
17 Correct 344 ms 420 KB Output is correct
18 Correct 322 ms 720 KB Output is correct
19 Correct 306 ms 644 KB Output is correct
20 Correct 266 ms 548 KB Output is correct
21 Correct 34 ms 620 KB Output is correct
22 Correct 50 ms 600 KB Output is correct
23 Correct 88 ms 548 KB Output is correct
24 Correct 5 ms 500 KB Output is correct
25 Correct 2 ms 500 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 413 ms 416 KB Output is correct
30 Correct 449 ms 420 KB Output is correct
31 Correct 380 ms 420 KB Output is correct
32 Correct 395 ms 416 KB Output is correct
33 Correct 431 ms 420 KB Output is correct
34 Correct 290 ms 544 KB Output is correct
35 Correct 303 ms 772 KB Output is correct
36 Correct 316 ms 652 KB Output is correct
37 Correct 417 ms 656 KB Output is correct
38 Correct 314 ms 660 KB Output is correct
39 Correct 374 ms 776 KB Output is correct
40 Correct 444 ms 668 KB Output is correct
41 Correct 295 ms 660 KB Output is correct
42 Correct 51 ms 632 KB Output is correct
43 Correct 63 ms 600 KB Output is correct
44 Correct 91 ms 560 KB Output is correct
45 Correct 104 ms 544 KB Output is correct
46 Correct 195 ms 544 KB Output is correct
47 Correct 242 ms 548 KB Output is correct
48 Correct 38 ms 692 KB Output is correct
49 Correct 40 ms 1000 KB Output is correct