oj.uz

Submission #1055034

# Submission time Handle Problem Language Result Execution time Memory
1055034 2024-08-12T14:09:45 Z Gromp15 Stations (IOI20_stations) C++17
52.3205 / 100
 552 ms 9072 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;

bool line = 1;
bool binary = 1;

const int N = 1001;
vector<vector<int>> go(N, vector<int>(N));

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++) {
		if (u[i] > v[i]) swap(u[i], v[i]);
		binary &= (v[i] + 1) / 2 == (u[i] + 1);
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	/*
	int r = -1;
	for (int i = 0; i < n; i++) {
		if (adj[i].size() == 1) r = i;
		line &= adj[i].size() <= 2;
	}
	if (line) {
		vector<int> ans(n);
		int t = 0;
		auto dfs = [&](auto&& s, int v, int p) -> void {
			ans[v] = t++;
			for (int u : adj[v]) if (u != p) s(s, u, v);
		};
		dfs(dfs, r, -1);
		return ans;
	}
	if (binary) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) go[i][j] = -1;
			auto dfs = [&](auto&& s, int v) -> void {
				for (int u : adj[v]) if (u != go[i][v]) {
					go[i][u] = v;
					s(s, u);
				}
			};
			dfs(dfs, i);
		}
		vector<int> ans(n);
		iota(ans.begin(), ans.end(), 0);
		return ans;
	}
	*/
	vector<int> tin(n), tout(n);
	int timer = 0;
	auto dfs = [&](auto&& s, int v, int p) -> void {
		tin[v] = timer++;
		for (int u : adj[v]) if (u != p) {
			s(s, u, v);
		}
		tout[v] = timer - 1;
	};
	dfs(dfs, 0, -1);
	vector<int> ans(n);
	for (int i = 0; i < n; i++) ans[i] = tin[i] * 1000 + tout[i];
	return ans;
}

bool anc(int x, int y) {
	int tins = x / 1000, touts = x % 1000;
	int tint = y / 1000, toutt = y % 1000;
	return tins <= tint && toutt <= touts;
}

int find_next_station(int s, int t, std::vector<int> c) {
	/*
	if (line) {
		for (int x : c) if ((x-s)*(x-t) <= 0) return x;
	}
	*/
	/*
	if (binary) {
		return go[t][s];
	}
	*/
	if (anc(s, t)) {
		for (int x : c) {
			if (anc(s, x) && anc(x, t)) return x;
		}
	}
	else {
		for (int x : c) {
			if (anc(x, s)) return x;
		}
	}
	assert(0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4440 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4440 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 8620 KB Output is correct
2 Correct 256 ms 8616 KB Output is correct
3 Correct 552 ms 8364 KB Output is correct
4 Correct 386 ms 8364 KB Output is correct
5 Correct 350 ms 8364 KB Output is correct
6 Correct 236 ms 8620 KB Output is correct
7 Correct 243 ms 8644 KB Output is correct
8 Correct 4 ms 8464 KB Output is correct
9 Correct 5 ms 8464 KB Output is correct
10 Correct 4 ms 8464 KB Output is correct
11 Correct 335 ms 8364 KB Output is correct
12 Correct 293 ms 8820 KB Output is correct
13 Correct 278 ms 8620 KB Output is correct
14 Correct 246 ms 8620 KB Output is correct
15 Correct 27 ms 8420 KB Output is correct
16 Correct 31 ms 8868 KB Output is correct
17 Correct 60 ms 8620 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 8364 KB Output is correct
2 Correct 399 ms 8368 KB Output is correct
3 Correct 382 ms 8364 KB Output is correct
4 Correct 4 ms 8452 KB Output is correct
5 Correct 5 ms 8456 KB Output is correct
6 Correct 3 ms 8456 KB Output is correct
7 Correct 338 ms 8364 KB Output is correct
8 Correct 506 ms 8400 KB Output is correct
9 Correct 391 ms 8364 KB Output is correct
10 Correct 343 ms 8364 KB Output is correct
11 Correct 5 ms 8456 KB Output is correct
12 Correct 5 ms 8456 KB Output is correct
13 Correct 5 ms 8456 KB Output is correct
14 Correct 4 ms 8608 KB Output is correct
15 Correct 4 ms 8468 KB Output is correct
16 Correct 278 ms 8368 KB Output is correct
17 Correct 287 ms 8364 KB Output is correct
18 Correct 289 ms 8364 KB Output is correct
19 Correct 307 ms 8364 KB Output is correct
20 Correct 295 ms 8364 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 300 ms 8620 KB Partially correct
2 Partially correct 257 ms 8620 KB Partially correct
3 Partially correct 514 ms 8364 KB Partially correct
4 Partially correct 374 ms 8364 KB Partially correct
5 Partially correct 368 ms 8364 KB Partially correct
6 Partially correct 277 ms 8620 KB Partially correct
7 Partially correct 265 ms 8620 KB Partially correct
8 Partially correct 4 ms 8464 KB Partially correct
9 Partially correct 5 ms 8460 KB Partially correct
10 Partially correct 4 ms 8496 KB Partially correct
11 Partially correct 286 ms 8620 KB Partially correct
12 Partially correct 302 ms 8620 KB Partially correct
13 Partially correct 523 ms 8364 KB Partially correct
14 Partially correct 405 ms 8364 KB Partially correct
15 Partially correct 328 ms 8364 KB Partially correct
16 Partially correct 227 ms 8620 KB Partially correct
17 Partially correct 337 ms 8364 KB Partially correct
18 Partially correct 248 ms 8620 KB Partially correct
19 Partially correct 257 ms 8832 KB Partially correct
20 Partially correct 237 ms 8620 KB Partially correct
21 Partially correct 27 ms 8452 KB Partially correct
22 Partially correct 36 ms 8688 KB Partially correct
23 Partially correct 51 ms 8776 KB Partially correct
24 Partially correct 6 ms 8456 KB Partially correct
25 Partially correct 6 ms 8452 KB Partially correct
26 Partially correct 6 ms 8456 KB Partially correct
27 Partially correct 6 ms 8764 KB Partially correct
28 Partially correct 4 ms 8452 KB Partially correct
29 Partially correct 279 ms 8388 KB Partially correct
30 Partially correct 279 ms 8364 KB Partially correct
31 Partially correct 299 ms 8364 KB Partially correct
32 Partially correct 276 ms 8364 KB Partially correct
33 Partially correct 273 ms 8368 KB Partially correct
34 Partially correct 180 ms 8620 KB Partially correct
35 Partially correct 242 ms 8868 KB Partially correct
36 Partially correct 261 ms 8620 KB Partially correct
37 Partially correct 257 ms 9072 KB Partially correct
38 Partially correct 274 ms 8868 KB Partially correct
39 Partially correct 242 ms 8868 KB Partially correct
40 Partially correct 277 ms 8880 KB Partially correct
41 Partially correct 267 ms 9072 KB Partially correct
42 Partially correct 33 ms 8712 KB Partially correct
43 Partially correct 55 ms 8660 KB Partially correct
44 Partially correct 69 ms 8704 KB Partially correct
45 Partially correct 84 ms 8688 KB Partially correct
46 Partially correct 179 ms 8620 KB Partially correct
47 Partially correct 177 ms 8620 KB Partially correct
48 Partially correct 40 ms 8708 KB Partially correct
49 Partially correct 37 ms 8904 KB Partially correct