oj.uz

Submission #956419

# Submission time Handle Problem Language Result Execution time Memory
956419 2024-04-01T19:28:49 Z Desh03 Stations (IOI20_stations) C++17
76 / 100
 614 ms 1548 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vector<int> in(n), en(n), d(n);
    int t = 0;
    auto dfs = [&](const auto &self, int u) -> void {
        in[u] = t++;
        for (int v : g[u]) {
            g[v].erase(find(g[v].begin(), g[v].end(), u));
            d[v] = d[u] + 1;
            self(self, v);
        }
        en[u] = t++;
    };
    dfs(dfs, 0);
    vector<int> id(n);
    for (int i = 0; i < n; i++) {
        if (d[i] % 2 == 0) {
            id[i] = in[i];
        } else {
            id[i] = en[i];
        }
    }
    return id;
}

int find_next_station(int s, int t, vector<int> c) {
    if (c[0] > s) {
        int in = s + 1;
        for (int i = 0; i < c.size() - 1; i++) {
            if (in <= t && t <= c[i]) {
                return c[i];
            }
            in = c[i] + 1;
        }
        return c.back();
    } else {
        int en = s;
        for (int i = c.size() - 1; i > 0; i--) {
            if (c[i] <= t && t <= en) {
                return c[i];
            }
            en = c[i] - 1;
        }
        return c[0];
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0; i < c.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 956 KB Output is correct
2 Correct 311 ms 960 KB Output is correct
3 Correct 546 ms 864 KB Output is correct
4 Correct 462 ms 684 KB Output is correct
5 Correct 347 ms 940 KB Output is correct
6 Correct 294 ms 1120 KB Output is correct
7 Correct 269 ms 940 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 346 ms 684 KB Output is correct
12 Correct 287 ms 1032 KB Output is correct
13 Correct 291 ms 1272 KB Output is correct
14 Correct 293 ms 684 KB Output is correct
15 Correct 38 ms 684 KB Output is correct
16 Correct 41 ms 1028 KB Output is correct
17 Correct 65 ms 1300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 684 KB Output is correct
2 Correct 387 ms 684 KB Output is correct
3 Correct 368 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 365 ms 684 KB Output is correct
8 Correct 567 ms 684 KB Output is correct
9 Correct 442 ms 684 KB Output is correct
10 Correct 386 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 856 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 3 ms 772 KB Output is correct
15 Correct 1 ms 764 KB Output is correct
16 Correct 315 ms 684 KB Output is correct
17 Correct 332 ms 684 KB Output is correct
18 Correct 328 ms 684 KB Output is correct
19 Correct 375 ms 684 KB Output is correct
20 Correct 352 ms 684 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 323 ms 964 KB Partially correct
2 Partially correct 309 ms 936 KB Partially correct
3 Correct 586 ms 948 KB Output is correct
4 Correct 445 ms 684 KB Output is correct
5 Correct 385 ms 684 KB Output is correct
6 Partially correct 343 ms 960 KB Partially correct
7 Partially correct 259 ms 684 KB Partially correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Partially correct 270 ms 868 KB Partially correct
12 Partially correct 376 ms 828 KB Partially correct
13 Correct 614 ms 684 KB Output is correct
14 Correct 468 ms 684 KB Output is correct
15 Correct 382 ms 684 KB Output is correct
16 Partially correct 330 ms 684 KB Partially correct
17 Correct 344 ms 684 KB Output is correct
18 Partially correct 295 ms 1264 KB Partially correct
19 Partially correct 300 ms 1548 KB Partially correct
20 Partially correct 299 ms 684 KB Partially correct
21 Correct 29 ms 772 KB Output is correct
22 Partially correct 36 ms 916 KB Partially correct
23 Partially correct 66 ms 1128 KB Partially correct
24 Correct 3 ms 964 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 2 ms 1020 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
28 Correct 0 ms 772 KB Output is correct
29 Correct 353 ms 684 KB Output is correct
30 Correct 340 ms 684 KB Output is correct
31 Correct 293 ms 684 KB Output is correct
32 Correct 330 ms 684 KB Output is correct
33 Correct 355 ms 684 KB Output is correct
34 Partially correct 183 ms 932 KB Partially correct
35 Partially correct 272 ms 1296 KB Partially correct
36 Partially correct 339 ms 1208 KB Partially correct
37 Partially correct 305 ms 1148 KB Partially correct
38 Partially correct 315 ms 1396 KB Partially correct
39 Partially correct 277 ms 972 KB Partially correct
40 Partially correct 278 ms 1408 KB Partially correct
41 Partially correct 314 ms 1152 KB Partially correct
42 Partially correct 41 ms 1092 KB Partially correct
43 Partially correct 58 ms 904 KB Partially correct
44 Partially correct 85 ms 912 KB Partially correct
45 Partially correct 104 ms 908 KB Partially correct
46 Partially correct 213 ms 860 KB Partially correct
47 Partially correct 230 ms 1172 KB Partially correct
48 Partially correct 30 ms 1212 KB Partially correct
49 Partially correct 36 ms 1404 KB Partially correct