oj.uz

Submission #306242

# Submission time Handle Problem Language Result Execution time Memory
306242 2020-09-25T01:50:21 Z qpwoeirut Stations (IOI20_stations) C++17
100 / 100
 999 ms 1392 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int MN = 1001;

set<int> adj[MN];
vector<int> lbl;

int cur;
void dfs(int node, int par, bool pre) {
    if (pre) lbl[node] = cur++;
    for (auto it=adj[node].begin(); it!=adj[node].end(); ++it) {
        if (*it == par) continue;
        dfs(*it, node, !pre);
    }
    if (!pre) lbl[node] = cur++;
}

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();
    }
    assert(u.size() == v.size());
    for (int i=0; i<u.size(); ++i) {
        adj[u[i]].insert(v[i]);
        adj[v[i]].insert(u[i]);
    }

    lbl = vector<int>(n);
    cur = 0;
    dfs(0, -1, true);
    //cerr << "lbl: "; for (int i=0; i<lbl.size(); ++i) { cerr << lbl[i] << ' ' ; } cerr << endl;
    return lbl;
}

int find_next_station(int s, int t, std::vector<int> c) {
    //cerr << "s,t,c: " << s << ' ' << t << ", "; for (int i=0; i<c.size(); ++i) cerr << c[i] << ' '; cerr << endl;
    assert(!c.empty());
    if (c.size() == 1) {
        return c[0];
    }
    if (s < c[0]) { // preorder
        if (s > t || t > c[c.size() - 2]) {
           return c.back();
        } else {
           return *lower_bound(c.begin(), c.end(), t);
        }
    } else if (s > c.back()) { // postorder
        if (s < t || t < c[1]) {
            return c[0];
        } else {
            int idx = upper_bound(c.begin(), c.end(), t) - c.begin();
            assert(idx > 0);
            return c[idx - 1];
        } 
    } else assert(false);
}
/*
1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3
*/

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 1044 KB Output is correct
2 Correct 456 ms 1240 KB Output is correct
3 Correct 980 ms 896 KB Output is correct
4 Correct 688 ms 896 KB Output is correct
5 Correct 773 ms 996 KB Output is correct
6 Correct 546 ms 1064 KB Output is correct
7 Correct 544 ms 1024 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 4 ms 988 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 1024 KB Output is correct
2 Correct 543 ms 1120 KB Output is correct
3 Correct 866 ms 896 KB Output is correct
4 Correct 675 ms 768 KB Output is correct
5 Correct 619 ms 988 KB Output is correct
6 Correct 496 ms 1136 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 1024 KB Output is correct
2 Correct 472 ms 1024 KB Output is correct
3 Correct 880 ms 896 KB Output is correct
4 Correct 672 ms 1016 KB Output is correct
5 Correct 687 ms 988 KB Output is correct
6 Correct 529 ms 1052 KB Output is correct
7 Correct 560 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 992 KB Output is correct
11 Correct 678 ms 980 KB Output is correct
12 Correct 556 ms 1048 KB Output is correct
13 Correct 460 ms 1056 KB Output is correct
14 Correct 483 ms 1128 KB Output is correct
15 Correct 69 ms 980 KB Output is correct
16 Correct 90 ms 928 KB Output is correct
17 Correct 140 ms 1116 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 896 KB Output is correct
2 Correct 703 ms 984 KB Output is correct
3 Correct 579 ms 984 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 2 ms 992 KB Output is correct
7 Correct 598 ms 896 KB Output is correct
8 Correct 999 ms 768 KB Output is correct
9 Correct 714 ms 768 KB Output is correct
10 Correct 611 ms 896 KB Output is correct
11 Correct 7 ms 980 KB Output is correct
12 Correct 5 ms 896 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 3 ms 988 KB Output is correct
15 Correct 2 ms 896 KB Output is correct
16 Correct 575 ms 896 KB Output is correct
17 Correct 504 ms 1168 KB Output is correct
18 Correct 581 ms 1160 KB Output is correct
19 Correct 533 ms 984 KB Output is correct
20 Correct 591 ms 1168 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 1036 KB Output is correct
2 Correct 462 ms 1048 KB Output is correct
3 Correct 921 ms 768 KB Output is correct
4 Correct 681 ms 1016 KB Output is correct
5 Correct 722 ms 1024 KB Output is correct
6 Correct 537 ms 1044 KB Output is correct
7 Correct 532 ms 1280 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 445 ms 1240 KB Output is correct
12 Correct 523 ms 1120 KB Output is correct
13 Correct 866 ms 896 KB Output is correct
14 Correct 683 ms 984 KB Output is correct
15 Correct 621 ms 1024 KB Output is correct
16 Correct 454 ms 1128 KB Output is correct
17 Correct 674 ms 896 KB Output is correct
18 Correct 476 ms 1024 KB Output is correct
19 Correct 547 ms 1024 KB Output is correct
20 Correct 499 ms 1016 KB Output is correct
21 Correct 76 ms 972 KB Output is correct
22 Correct 92 ms 1104 KB Output is correct
23 Correct 149 ms 1024 KB Output is correct
24 Correct 6 ms 768 KB Output is correct
25 Correct 6 ms 984 KB Output is correct
26 Correct 5 ms 996 KB Output is correct
27 Correct 4 ms 996 KB Output is correct
28 Correct 1 ms 988 KB Output is correct
29 Correct 512 ms 992 KB Output is correct
30 Correct 542 ms 988 KB Output is correct
31 Correct 567 ms 932 KB Output is correct
32 Correct 546 ms 988 KB Output is correct
33 Correct 509 ms 988 KB Output is correct
34 Correct 394 ms 1068 KB Output is correct
35 Correct 450 ms 1280 KB Output is correct
36 Correct 449 ms 1016 KB Output is correct
37 Correct 454 ms 1216 KB Output is correct
38 Correct 596 ms 1008 KB Output is correct
39 Correct 532 ms 1024 KB Output is correct
40 Correct 422 ms 1088 KB Output is correct
41 Correct 537 ms 1024 KB Output is correct
42 Correct 71 ms 896 KB Output is correct
43 Correct 140 ms 1120 KB Output is correct
44 Correct 158 ms 1280 KB Output is correct
45 Correct 212 ms 1024 KB Output is correct
46 Correct 329 ms 1024 KB Output is correct
47 Correct 405 ms 1084 KB Output is correct
48 Correct 65 ms 1392 KB Output is correct
49 Correct 54 ms 1124 KB Output is correct