oj.uz

Submission #1073736

# Submission time Handle Problem Language Result Execution time Memory
1073736 2024-08-24T19:35:40 Z allin27x Stations (IOI20_stations) C++17
52.3205 / 100
 651 ms 1188 KB 
#include <bits/stdc++.h>
using namespace std;
#include "stations.h"

const int N = 1001;
vector<int> adj[N];
int tin[N];
int tout[N];
int tp = 0;

void dfs(int i, int p) {
	tin[i] = tp++;
	for (int c: adj[i]) {
		if (c == p) continue;
		dfs(c,i);
	}
	tout[i] = tp;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for (int i=0; i<n; i++) adj[i].clear();
	std::vector<int> labels(n);
	for (int i=0; i<n-1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	tp = 0;
	dfs(0,0);
	for (int i=0; i<n; i++) labels[i] = 1000*tin[i] + tout[i]-1;
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int s_in = s/1000; int s_out = s%1000;
	int t_in = t/1000; int t_out = t%1000;
	if (s_in <= t_in && t_out <= s_out) {
		// t is below s
		for (int x: c) {
			int x_in = x/1000; int x_out = x%1000;
			if (x_in < s_in) continue;
			if (x_in <= t_in && t_out <= x_out) return x;
		}
	} else {
		for (int x: c) {
			if (x/1000 < s_in) return x;
		}
	}
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 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 344 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 353 ms 804 KB Output is correct
2 Correct 299 ms 684 KB Output is correct
3 Correct 590 ms 684 KB Output is correct
4 Correct 453 ms 684 KB Output is correct
5 Correct 384 ms 684 KB Output is correct
6 Correct 299 ms 684 KB Output is correct
7 Correct 349 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 3 ms 764 KB Output is correct
10 Correct 1 ms 776 KB Output is correct
11 Correct 424 ms 684 KB Output is correct
12 Correct 325 ms 792 KB Output is correct
13 Correct 340 ms 784 KB Output is correct
14 Correct 247 ms 684 KB Output is correct
15 Correct 30 ms 764 KB Output is correct
16 Correct 37 ms 684 KB Output is correct
17 Correct 59 ms 800 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 684 KB Output is correct
2 Correct 475 ms 684 KB Output is correct
3 Correct 389 ms 684 KB Output is correct
4 Correct 2 ms 776 KB Output is correct
5 Correct 1 ms 776 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 443 ms 684 KB Output is correct
8 Correct 631 ms 684 KB Output is correct
9 Correct 480 ms 940 KB Output is correct
10 Correct 423 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 764 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 2 ms 776 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 353 ms 684 KB Output is correct
17 Correct 354 ms 684 KB Output is correct
18 Correct 368 ms 684 KB Output is correct
19 Correct 352 ms 684 KB Output is correct
20 Correct 345 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 348 ms 684 KB Partially correct
2 Partially correct 313 ms 712 KB Partially correct
3 Partially correct 618 ms 684 KB Partially correct
4 Partially correct 456 ms 684 KB Partially correct
5 Partially correct 417 ms 684 KB Partially correct
6 Partially correct 303 ms 684 KB Partially correct
7 Partially correct 353 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 2 ms 776 KB Partially correct
10 Partially correct 1 ms 776 KB Partially correct
11 Partially correct 340 ms 800 KB Partially correct
12 Partially correct 375 ms 684 KB Partially correct
13 Partially correct 646 ms 684 KB Partially correct
14 Partially correct 468 ms 684 KB Partially correct
15 Partially correct 406 ms 684 KB Partially correct
16 Partially correct 293 ms 684 KB Partially correct
17 Partially correct 450 ms 684 KB Partially correct
18 Partially correct 299 ms 792 KB Partially correct
19 Partially correct 341 ms 788 KB Partially correct
20 Partially correct 319 ms 684 KB Partially correct
21 Partially correct 27 ms 768 KB Partially correct
22 Partially correct 36 ms 764 KB Partially correct
23 Partially correct 49 ms 768 KB Partially correct
24 Partially correct 2 ms 764 KB Partially correct
25 Partially correct 2 ms 768 KB Partially correct
26 Partially correct 2 ms 768 KB Partially correct
27 Partially correct 1 ms 776 KB Partially correct
28 Partially correct 0 ms 768 KB Partially correct
29 Partially correct 362 ms 684 KB Partially correct
30 Partially correct 322 ms 684 KB Partially correct
31 Partially correct 368 ms 712 KB Partially correct
32 Partially correct 380 ms 684 KB Partially correct
33 Partially correct 375 ms 684 KB Partially correct
34 Partially correct 199 ms 684 KB Partially correct
35 Partially correct 279 ms 684 KB Partially correct
36 Partially correct 313 ms 684 KB Partially correct
37 Partially correct 304 ms 932 KB Partially correct
38 Partially correct 356 ms 792 KB Partially correct
39 Partially correct 275 ms 796 KB Partially correct
40 Partially correct 350 ms 1188 KB Partially correct
41 Partially correct 292 ms 1044 KB Partially correct
42 Partially correct 31 ms 768 KB Partially correct
43 Partially correct 69 ms 716 KB Partially correct
44 Partially correct 82 ms 688 KB Partially correct
45 Partially correct 107 ms 896 KB Partially correct
46 Partially correct 205 ms 684 KB Partially correct
47 Partially correct 203 ms 716 KB Partially correct
48 Partially correct 32 ms 760 KB Partially correct
49 Partially correct 31 ms 764 KB Partially correct