oj.uz

Submission #308579

# Submission time Handle Problem Language Result Execution time Memory
308579 2020-10-01T14:48:05 Z lacito Stations (IOI20_stations) C++14
31.0422 / 100
 1020 ms 1024 KB 
#include "stations.h"
#include <vector>

using namespace std;

const int M = 2000;

vector<vector<int>> g;
vector<int> intime, outtime;
int time;

void dfs(int v) {
    intime[v] = time++;
    for (int x : g[v])
        if (intime[x] == -1)
            dfs(x);
    outtime[v] = time++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	g.assign(n, {});
	intime.assign(n, -1);
	outtime.assign(n, -1);
	for (int i = 0; i < n - 1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
	}
	time = 0;
	dfs(0);
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = M * intime[i] + outtime[i];
	}
	return labels;
}

inline int in(int label) {
    return label / M;
}

inline int out(int label) {
    return label % M;
}

inline bool inside(int label_a, int label_b) {
    return in(label_a) <= in(label_b) && out(label_b) <= out(label_a);
}

int find_next_station(int s, int t, vector<int> c) {
    int parent = -1;
    for (int x : c) {
        if (inside(x, s))
            parent = x;
    }
    for (int x : c) {
        if (inside(x, t) && x != parent)
            return x;
    }
	return parent;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=14014
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=0, label=1991
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 656 KB Output is correct
2 Correct 747 ms 656 KB Output is correct
3 Correct 718 ms 656 KB Output is correct
4 Correct 3 ms 660 KB Output is correct
5 Correct 8 ms 656 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 638 ms 640 KB Output is correct
8 Correct 974 ms 768 KB Output is correct
9 Correct 693 ms 844 KB Output is correct
10 Correct 680 ms 772 KB Output is correct
11 Correct 6 ms 796 KB Output is correct
12 Correct 6 ms 664 KB Output is correct
13 Correct 4 ms 696 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Correct 563 ms 640 KB Output is correct
17 Correct 626 ms 660 KB Output is correct
18 Correct 587 ms 652 KB Output is correct
19 Correct 670 ms 640 KB Output is correct
20 Correct 577 ms 896 KB Output is correct

Subtask #5
21.0422 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 625 ms 1024 KB Partially correct
2 Partially correct 544 ms 776 KB Partially correct
3 Partially correct 1020 ms 640 KB Partially correct
4 Partially correct 863 ms 652 KB Partially correct
5 Partially correct 644 ms 640 KB Partially correct
6 Partially correct 515 ms 796 KB Partially correct
7 Partially correct 467 ms 816 KB Partially correct
8 Partially correct 3 ms 640 KB Partially correct
9 Partially correct 4 ms 640 KB Partially correct
10 Partially correct 2 ms 640 KB Partially correct
11 Partially correct 559 ms 1004 KB Partially correct
12 Partially correct 565 ms 836 KB Partially correct
13 Partially correct 947 ms 764 KB Partially correct
14 Partially correct 750 ms 964 KB Partially correct
15 Partially correct 761 ms 640 KB Partially correct
16 Partially correct 540 ms 768 KB Partially correct
17 Partially correct 648 ms 660 KB Partially correct
18 Partially correct 555 ms 744 KB Partially correct
19 Partially correct 526 ms 944 KB Partially correct
20 Partially correct 535 ms 768 KB Partially correct
21 Partially correct 65 ms 644 KB Partially correct
22 Partially correct 75 ms 864 KB Partially correct
23 Partially correct 132 ms 824 KB Partially correct
24 Partially correct 6 ms 664 KB Partially correct
25 Partially correct 5 ms 660 KB Partially correct
26 Partially correct 5 ms 640 KB Partially correct
27 Partially correct 4 ms 664 KB Partially correct
28 Partially correct 1 ms 640 KB Partially correct
29 Partially correct 603 ms 652 KB Partially correct
30 Partially correct 587 ms 664 KB Partially correct
31 Partially correct 624 ms 656 KB Partially correct
32 Partially correct 522 ms 656 KB Partially correct
33 Partially correct 597 ms 640 KB Partially correct
34 Partially correct 296 ms 1024 KB Partially correct
35 Partially correct 402 ms 800 KB Partially correct
36 Partially correct 559 ms 1024 KB Partially correct
37 Partially correct 631 ms 832 KB Partially correct
38 Partially correct 466 ms 760 KB Partially correct
39 Partially correct 463 ms 804 KB Partially correct
40 Partially correct 460 ms 812 KB Partially correct
41 Partially correct 579 ms 872 KB Partially correct
42 Partially correct 84 ms 844 KB Partially correct
43 Partially correct 140 ms 816 KB Partially correct
44 Partially correct 134 ms 768 KB Partially correct
45 Partially correct 160 ms 768 KB Partially correct
46 Partially correct 337 ms 848 KB Partially correct
47 Partially correct 388 ms 812 KB Partially correct
48 Partially correct 61 ms 912 KB Partially correct
49 Partially correct 83 ms 896 KB Partially correct