Submission #809037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
809037	2023-08-05T14:28:38 Z	adrilen	Stations (IOI20_stations)	C++17	5 / 100	809 ms	712 KB

stations

#include "stations.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1e3;


vector <int> output;

int t;
void dfs(const vector<vector<int>> &adj, int p, int par)
{
	output[p] = t++;
	for (int i : adj[p])
	{
		if (i == par) continue;
		dfs(adj, i, p);
	}
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> adj(n);

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

	int start = -1;
	t = 0;
	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 1ull) {
			start = i;
			break;
		}
	}

	output.assign(n, 0);
	dfs(adj, start, -1);
	return output;
}

int find_next_station(int s, int T, std::vector<int> c) {

	if (c.size() == 1ull) return c.front();

	if (T < c.front()) return c.front();


	auto it = upper_bound(c.begin(), c.end(), T) - 1;


	return *it;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	544 KB	Output is correct
2	Correct	373 ms	624 KB	Output is correct
3	Correct	667 ms	416 KB	Output is correct
4	Correct	576 ms	504 KB	Output is correct
5	Correct	448 ms	548 KB	Output is correct
6	Correct	390 ms	544 KB	Output is correct
7	Correct	294 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	492 KB	Output is correct

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	313 ms	636 KB	Wrong query response.
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	478 ms	636 KB	Output is correct
2	Correct	323 ms	632 KB	Output is correct
3	Correct	809 ms	416 KB	Output is correct
4	Correct	565 ms	420 KB	Output is correct
5	Correct	530 ms	504 KB	Output is correct
6	Correct	384 ms	612 KB	Output is correct
7	Correct	401 ms	496 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	3 ms	492 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	562 ms	500 KB	Output is correct
12	Incorrect	421 ms	712 KB	Wrong query response.
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	785 ms	508 KB	Output is correct
2	Correct	514 ms	416 KB	Output is correct
3	Correct	487 ms	416 KB	Output is correct
4	Correct	2 ms	496 KB	Output is correct
5	Correct	4 ms	492 KB	Output is correct
6	Correct	0 ms	492 KB	Output is correct
7	Correct	475 ms	484 KB	Output is correct
8	Correct	674 ms	436 KB	Output is correct
9	Correct	532 ms	416 KB	Output is correct
10	Correct	470 ms	504 KB	Output is correct
11	Incorrect	2 ms	496 KB	Wrong query response.
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	389 ms	544 KB	Output is correct
2	Correct	304 ms	612 KB	Output is correct
3	Correct	762 ms	416 KB	Output is correct
4	Correct	510 ms	508 KB	Output is correct
5	Correct	404 ms	416 KB	Output is correct
6	Correct	395 ms	636 KB	Output is correct
7	Correct	386 ms	508 KB	Output is correct
8	Correct	1 ms	496 KB	Output is correct
9	Correct	2 ms	500 KB	Output is correct
10	Correct	0 ms	492 KB	Output is correct
11	Incorrect	412 ms	540 KB	Wrong query response.
12	Halted	0 ms	0 KB	-