oj.uz

Submission #305498

# Submission time Handle Problem Language Result Execution time Memory
305498 2020-09-23T11:00:15 Z JustInCase Stations (IOI20_stations) C++17
52.3205 / 100
 1069 ms 1280 KB 
#include "stations.h"
#include <vector>
#include <iostream>

#define int32_t int
#define int64_t long long

const int32_t MAX_N = 1000;

struct Vertex {
	int32_t inTime, outTime;
	std::vector< int32_t > v;
};

Vertex g[MAX_N + 5];

void dfs(int32_t u, int32_t &t, int32_t par) {
	g[u].inTime = t;

	for(auto &v : g[u].v) {
		if(v != par) {
			t++;
			dfs(v, t, u);
		}
	}

	g[u].outTime = t;
}

std::vector< int32_t > label(int32_t n, int32_t k, std::vector< int32_t > u, std::vector< int32_t > v) {
	for(int32_t i = 0; i < n; i++) {
		g[i].v.clear();
	}

	for(int32_t i = 0; i < n - 1; i++) {
		g[u[i]].v.push_back(v[i]);
		g[v[i]].v.push_back(u[i]);
	}
	
	int32_t t = 0;
	dfs(0, t, -1);
	
	std::vector< int32_t > labels(n);
	for(int32_t i = 0; i < n; i++) {
		labels[i] = 1000 * g[i].inTime + g[i].outTime;
	}

	return labels;
}

int32_t find_next_station(int32_t s, int32_t t, std::vector< int32_t > c) {
	int32_t lS = s / 1000;
	int32_t rS = s % 1000;
	
	int32_t lT = t / 1000;
	int32_t rT = t / 1000;

	if(lS <= lT && rS >= rT) {
		for(auto &x : c) {
			int32_t lX = x / 1000;
			int32_t rX = x % 1000;

			if(lX < lS) {
				continue;
			}

			if(lX <= lT && rX >= rT) {
				return x;
			}
		}
	}
	else {
		for(auto &x : c) {
			int32_t lX = x / 1000;

			if(lX < lS) {
				return x;
			}
		}
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 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 5 ms 384 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 573 ms 1024 KB Output is correct
2 Correct 472 ms 1008 KB Output is correct
3 Correct 897 ms 768 KB Output is correct
4 Correct 676 ms 880 KB Output is correct
5 Correct 600 ms 1160 KB Output is correct
6 Correct 487 ms 1024 KB Output is correct
7 Correct 490 ms 1040 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 868 KB Output is correct
10 Correct 2 ms 868 KB Output is correct
11 Correct 603 ms 768 KB Output is correct
12 Correct 498 ms 1260 KB Output is correct
13 Correct 474 ms 1008 KB Output is correct
14 Correct 538 ms 820 KB Output is correct
15 Correct 59 ms 1024 KB Output is correct
16 Correct 74 ms 956 KB Output is correct
17 Correct 119 ms 932 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 872 KB Output is correct
2 Correct 749 ms 864 KB Output is correct
3 Correct 671 ms 880 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 4 ms 876 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 657 ms 768 KB Output is correct
8 Correct 1065 ms 768 KB Output is correct
9 Correct 729 ms 872 KB Output is correct
10 Correct 663 ms 768 KB Output is correct
11 Correct 6 ms 876 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 5 ms 876 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 547 ms 768 KB Output is correct
17 Correct 611 ms 868 KB Output is correct
18 Correct 627 ms 768 KB Output is correct
19 Correct 596 ms 868 KB Output is correct
20 Correct 626 ms 768 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 561 ms 1008 KB Partially correct
2 Partially correct 516 ms 1024 KB Partially correct
3 Partially correct 1015 ms 768 KB Partially correct
4 Partially correct 697 ms 768 KB Partially correct
5 Partially correct 604 ms 768 KB Partially correct
6 Partially correct 500 ms 1024 KB Partially correct
7 Partially correct 467 ms 896 KB Partially correct
8 Partially correct 4 ms 868 KB Partially correct
9 Partially correct 6 ms 768 KB Partially correct
10 Partially correct 2 ms 768 KB Partially correct
11 Partially correct 476 ms 812 KB Partially correct
12 Partially correct 567 ms 816 KB Partially correct
13 Partially correct 921 ms 896 KB Partially correct
14 Partially correct 948 ms 768 KB Partially correct
15 Partially correct 617 ms 872 KB Partially correct
16 Partially correct 578 ms 816 KB Partially correct
17 Partially correct 587 ms 872 KB Partially correct
18 Partially correct 611 ms 888 KB Partially correct
19 Partially correct 614 ms 1120 KB Partially correct
20 Partially correct 601 ms 768 KB Partially correct
21 Partially correct 63 ms 852 KB Partially correct
22 Partially correct 85 ms 1024 KB Partially correct
23 Partially correct 158 ms 896 KB Partially correct
24 Partially correct 6 ms 868 KB Partially correct
25 Partially correct 6 ms 876 KB Partially correct
26 Partially correct 6 ms 768 KB Partially correct
27 Partially correct 5 ms 868 KB Partially correct
28 Partially correct 2 ms 868 KB Partially correct
29 Partially correct 602 ms 768 KB Partially correct
30 Partially correct 586 ms 1044 KB Partially correct
31 Partially correct 686 ms 896 KB Partially correct
32 Partially correct 548 ms 1024 KB Partially correct
33 Partially correct 563 ms 768 KB Partially correct
34 Partially correct 437 ms 768 KB Partially correct
35 Partially correct 450 ms 1280 KB Partially correct
36 Partially correct 464 ms 1128 KB Partially correct
37 Partially correct 469 ms 892 KB Partially correct
38 Partially correct 458 ms 792 KB Partially correct
39 Partially correct 447 ms 772 KB Partially correct
40 Partially correct 455 ms 1028 KB Partially correct
41 Partially correct 454 ms 780 KB Partially correct
42 Partially correct 62 ms 952 KB Partially correct
43 Partially correct 107 ms 1076 KB Partially correct
44 Partially correct 129 ms 784 KB Partially correct
45 Partially correct 164 ms 788 KB Partially correct
46 Partially correct 351 ms 768 KB Partially correct
47 Partially correct 315 ms 768 KB Partially correct
48 Partially correct 76 ms 768 KB Partially correct
49 Partially correct 72 ms 1024 KB Partially correct