oj.uz

Submission #304916

# Submission time Handle Problem Language Result Execution time Memory
304916 2020-09-22T07:49:41 Z kevinsogo Stations (IOI20_stations) C++17
100 / 100
 1394 ms 1088 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

struct Labeller {
    int n, ord = 0;
    vector<vector<int>> adj;
    vector<int> labels;
    Labeller(int n, const vector<int>& u, const vector<int>& v): n(n), adj(n), labels(n) {
        for (int i = 0; i < n - 1; i++) {
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);
        }
        preposterous(0, -1, false);
        assert(ord == n);
    }

    void preposterous(int s, int p, bool x) {
        if (x) labels[s] = ord++;
        for (int t : adj[s]) if (t != p) preposterous(t, s, !x);
        if (!x) labels[s] = ord++;
    }
};

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    return Labeller(n, u, v).labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s > c.back()) reverse(c.begin(), c.end());
    for (int u : c) if (min(u, s) <= t && t <= max(u, s)) return u;
    return c.back();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 1036 KB Output is correct
2 Correct 605 ms 1032 KB Output is correct
3 Correct 1049 ms 904 KB Output is correct
4 Correct 853 ms 640 KB Output is correct
5 Correct 755 ms 640 KB Output is correct
6 Correct 577 ms 1036 KB Output is correct
7 Correct 558 ms 768 KB Output is correct
8 Correct 4 ms 776 KB Output is correct
9 Correct 4 ms 812 KB Output is correct
10 Correct 1 ms 640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 896 KB Output is correct
2 Correct 785 ms 776 KB Output is correct
3 Correct 1079 ms 744 KB Output is correct
4 Correct 912 ms 640 KB Output is correct
5 Correct 686 ms 640 KB Output is correct
6 Correct 626 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 1012 KB Output is correct
2 Correct 552 ms 1000 KB Output is correct
3 Correct 929 ms 752 KB Output is correct
4 Correct 857 ms 752 KB Output is correct
5 Correct 767 ms 640 KB Output is correct
6 Correct 595 ms 992 KB Output is correct
7 Correct 578 ms 984 KB Output is correct
8 Correct 3 ms 752 KB Output is correct
9 Correct 5 ms 684 KB Output is correct
10 Correct 2 ms 916 KB Output is correct
11 Correct 676 ms 776 KB Output is correct
12 Correct 531 ms 1024 KB Output is correct
13 Correct 623 ms 1000 KB Output is correct
14 Correct 596 ms 772 KB Output is correct
15 Correct 63 ms 784 KB Output is correct
16 Correct 74 ms 768 KB Output is correct
17 Correct 148 ms 760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1013 ms 760 KB Output is correct
2 Correct 758 ms 748 KB Output is correct
3 Correct 816 ms 788 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 785 ms 640 KB Output is correct
8 Correct 1172 ms 832 KB Output is correct
9 Correct 810 ms 800 KB Output is correct
10 Correct 785 ms 752 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 7 ms 832 KB Output is correct
14 Correct 5 ms 776 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 604 ms 768 KB Output is correct
17 Correct 621 ms 776 KB Output is correct
18 Correct 693 ms 640 KB Output is correct
19 Correct 554 ms 880 KB Output is correct
20 Correct 714 ms 916 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 984 KB Output is correct
2 Correct 620 ms 1008 KB Output is correct
3 Correct 1394 ms 748 KB Output is correct
4 Correct 897 ms 872 KB Output is correct
5 Correct 800 ms 764 KB Output is correct
6 Correct 527 ms 1040 KB Output is correct
7 Correct 608 ms 744 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 800 KB Output is correct
11 Correct 510 ms 904 KB Output is correct
12 Correct 573 ms 816 KB Output is correct
13 Correct 1236 ms 960 KB Output is correct
14 Correct 843 ms 896 KB Output is correct
15 Correct 751 ms 872 KB Output is correct
16 Correct 518 ms 752 KB Output is correct
17 Correct 699 ms 872 KB Output is correct
18 Correct 557 ms 1016 KB Output is correct
19 Correct 584 ms 1048 KB Output is correct
20 Correct 500 ms 776 KB Output is correct
21 Correct 95 ms 768 KB Output is correct
22 Correct 76 ms 752 KB Output is correct
23 Correct 150 ms 760 KB Output is correct
24 Correct 8 ms 768 KB Output is correct
25 Correct 5 ms 640 KB Output is correct
26 Correct 5 ms 776 KB Output is correct
27 Correct 4 ms 776 KB Output is correct
28 Correct 2 ms 776 KB Output is correct
29 Correct 644 ms 888 KB Output is correct
30 Correct 570 ms 936 KB Output is correct
31 Correct 589 ms 756 KB Output is correct
32 Correct 602 ms 756 KB Output is correct
33 Correct 686 ms 768 KB Output is correct
34 Correct 354 ms 768 KB Output is correct
35 Correct 576 ms 1016 KB Output is correct
36 Correct 530 ms 1024 KB Output is correct
37 Correct 524 ms 856 KB Output is correct
38 Correct 545 ms 840 KB Output is correct
39 Correct 404 ms 836 KB Output is correct
40 Correct 451 ms 852 KB Output is correct
41 Correct 623 ms 896 KB Output is correct
42 Correct 102 ms 768 KB Output is correct
43 Correct 131 ms 792 KB Output is correct
44 Correct 146 ms 896 KB Output is correct
45 Correct 184 ms 780 KB Output is correct
46 Correct 342 ms 1024 KB Output is correct
47 Correct 389 ms 780 KB Output is correct
48 Correct 74 ms 800 KB Output is correct
49 Correct 92 ms 1088 KB Output is correct