oj.uz

Submission #780814

# Submission time Handle Problem Language Result Execution time Memory
780814 2023-07-12T13:28:54 Z Elias Stations (IOI20_stations) C++17
100 / 100
 757 ms 736 KB 
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

#ifndef _DEBUG
#include "stations.h"
#endif

#ifdef _DEBUG

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v);
int find_next_station(int s, int t, std::vector<int> c);

#endif

vector<int> l;
int timer;

vector<vector<int>> adj;

void dfs(int i, int p)
{
	if (p == -1 || l[p] == -1)
		l[i] = timer++;
	for (int c : adj[i])
		if (c != p)
			dfs(c, i);
	if (l[i] == -1)
		l[i] = timer++;
}

vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v)
{
	timer = 0;
	l.assign(n, -1);
	adj.assign(n, {});

	for (int i = 0; i < n - 1; i++)
	{
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, -1);

	return l;
}

int find_next_station(int s, int t, std::vector<int> c)
{
	if (s > c.back())
	{ // is larger than all adjacent
		reverse(c.begin(), c.end());
		if (t > s)
			return c.back();

		for (int other : c)
		{
			if (t >= other)
				return other;
		}
		return c.back();
	}
	else
	{ // is smaller than all adjacent
		if (t < s)
			return c.back(); // is not in subtree, as s is the smallest in the subtree
		for (int other : c)
		{
			if (t <= other)
				return other;
		}
		return c.back();
	}
}

#ifdef _DEBUG

static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main()
{
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++)
	{
		assert(scanf("%d%d", &n, &k) == 2);
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++)
		{
			assert(scanf("%d%d", &u[i], &v[i]) == 2);
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n)
		{
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++)
		{
			if (labels[i] < 0 || labels[i] > k)
			{
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end())
			{
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label)
			{
				max_label = labels[i];
			}
		}
		assert(scanf("%d", &q) == 1);
		for (int i = 0; i < q; i++)
		{
			assert(scanf("%d%d%d", &s, &t, &w) == 3);
			c.clear();
			for (int v : adjlist[s])
			{
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer))
			{
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers)
	{
		printf("%d\n", index);
	}
	exit(0);
}

#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 548 KB Output is correct
2 Correct 334 ms 544 KB Output is correct
3 Correct 741 ms 420 KB Output is correct
4 Correct 431 ms 416 KB Output is correct
5 Correct 539 ms 556 KB Output is correct
6 Correct 412 ms 536 KB Output is correct
7 Correct 406 ms 508 KB Output is correct
8 Correct 2 ms 484 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 632 KB Output is correct
2 Correct 427 ms 672 KB Output is correct
3 Correct 695 ms 496 KB Output is correct
4 Correct 507 ms 540 KB Output is correct
5 Correct 536 ms 500 KB Output is correct
6 Correct 324 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 676 KB Output is correct
2 Correct 327 ms 672 KB Output is correct
3 Correct 683 ms 508 KB Output is correct
4 Correct 496 ms 420 KB Output is correct
5 Correct 518 ms 508 KB Output is correct
6 Correct 384 ms 624 KB Output is correct
7 Correct 400 ms 544 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 581 ms 420 KB Output is correct
12 Correct 390 ms 672 KB Output is correct
13 Correct 413 ms 620 KB Output is correct
14 Correct 379 ms 504 KB Output is correct
15 Correct 41 ms 472 KB Output is correct
16 Correct 42 ms 572 KB Output is correct
17 Correct 63 ms 508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 416 KB Output is correct
2 Correct 459 ms 504 KB Output is correct
3 Correct 501 ms 420 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 533 ms 416 KB Output is correct
8 Correct 716 ms 512 KB Output is correct
9 Correct 529 ms 420 KB Output is correct
10 Correct 483 ms 504 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 4 ms 500 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 481 ms 500 KB Output is correct
17 Correct 448 ms 416 KB Output is correct
18 Correct 492 ms 508 KB Output is correct
19 Correct 428 ms 420 KB Output is correct
20 Correct 457 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 676 KB Output is correct
2 Correct 381 ms 632 KB Output is correct
3 Correct 747 ms 416 KB Output is correct
4 Correct 420 ms 500 KB Output is correct
5 Correct 459 ms 504 KB Output is correct
6 Correct 421 ms 544 KB Output is correct
7 Correct 302 ms 544 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 328 ms 632 KB Output is correct
12 Correct 491 ms 548 KB Output is correct
13 Correct 757 ms 512 KB Output is correct
14 Correct 527 ms 508 KB Output is correct
15 Correct 449 ms 508 KB Output is correct
16 Correct 381 ms 544 KB Output is correct
17 Correct 524 ms 484 KB Output is correct
18 Correct 361 ms 616 KB Output is correct
19 Correct 394 ms 712 KB Output is correct
20 Correct 386 ms 532 KB Output is correct
21 Correct 49 ms 496 KB Output is correct
22 Correct 52 ms 544 KB Output is correct
23 Correct 79 ms 548 KB Output is correct
24 Correct 3 ms 500 KB Output is correct
25 Correct 3 ms 496 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 488 KB Output is correct
29 Correct 476 ms 416 KB Output is correct
30 Correct 464 ms 416 KB Output is correct
31 Correct 458 ms 504 KB Output is correct
32 Correct 401 ms 512 KB Output is correct
33 Correct 375 ms 508 KB Output is correct
34 Correct 262 ms 672 KB Output is correct
35 Correct 358 ms 628 KB Output is correct
36 Correct 320 ms 632 KB Output is correct
37 Correct 421 ms 736 KB Output is correct
38 Correct 381 ms 712 KB Output is correct
39 Correct 336 ms 628 KB Output is correct
40 Correct 346 ms 704 KB Output is correct
41 Correct 350 ms 620 KB Output is correct
42 Correct 40 ms 576 KB Output is correct
43 Correct 83 ms 644 KB Output is correct
44 Correct 109 ms 556 KB Output is correct
45 Correct 118 ms 548 KB Output is correct
46 Correct 232 ms 504 KB Output is correct
47 Correct 216 ms 544 KB Output is correct
48 Correct 35 ms 604 KB Output is correct
49 Correct 52 ms 720 KB Output is correct