oj.uz

Submission #468376

# Submission time Handle Problem Language Result Execution time Memory
468376 2021-08-27T21:39:53 Z kessido Stations (IOI20_stations) C++17
100 / 100
 1128 ms 780 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define vll vector<ll>
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define fori(i,n) for(int i = 0; i < int(n); ++i)

vi label(int n, int k, vi u, vi v) {
    vvi e(n);
    fori(i,n-1){
        e[u[i]].push_back(v[i]);
        e[v[i]].push_back(u[i]);
    }
    int cur_label = 0;
    vi res(n, -1);
    auto dfs = [&](auto& self, int i, int parent, int depth) -> void {
        if(depth) res[i] = cur_label++;
        for(int j : e[i]) {
            if(j==parent) continue;
            self(self, j, i, depth^1);
        }
        if(!depth) res[i] = cur_label++;
    };
    dfs(dfs, 0, -1, 1);
    assert(res[0] == 0);
    assert(cur_label==n);
    return res;
}

int find_next_station(int s, int t, vi c) {
    if(c.size() == 1) return c[0];
    if(s==t) return s;

    sort(all(c));

    int i = 0;
    if(s == 0) {
        // root
        while(i < c.size() && c[i] < t) i++;
    } else if (c.back() < s) {
        // case 1, s "end"
        if(t > s) return c.front();
        while(i + 1 < c.size() && c[i + 1] <= t) i++;
    } else {
        // case 2, s is "start"
        if(t < s || c.back() < t) return c.back();
        while(i < c.size() && c[i] < t) i++;
    }
    if(c.size() <= i) return c.front();
    assert(i < c.size());
    return c[i];

}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(i < c.size() && c[i] < t) i++;
      |               ~~^~~~~~~~~~
stations.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(i + 1 < c.size() && c[i + 1] <= t) i++;
      |               ~~~~~~^~~~~~~~~~
stations.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(i < c.size() && c[i] < t) i++;
      |               ~~^~~~~~~~~~
stations.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(c.size() <= i) return c.front();
      |        ~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from stations.cpp:2:
stations.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     assert(i < c.size());
      |            ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 528 KB Output is correct
2 Correct 502 ms 528 KB Output is correct
3 Correct 1047 ms 400 KB Output is correct
4 Correct 722 ms 400 KB Output is correct
5 Correct 685 ms 400 KB Output is correct
6 Correct 570 ms 488 KB Output is correct
7 Correct 559 ms 476 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 1 ms 476 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 604 KB Output is correct
2 Correct 612 ms 528 KB Output is correct
3 Correct 1128 ms 400 KB Output is correct
4 Correct 766 ms 484 KB Output is correct
5 Correct 697 ms 400 KB Output is correct
6 Correct 517 ms 656 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 620 KB Output is correct
2 Correct 597 ms 520 KB Output is correct
3 Correct 929 ms 400 KB Output is correct
4 Correct 815 ms 484 KB Output is correct
5 Correct 667 ms 400 KB Output is correct
6 Correct 556 ms 528 KB Output is correct
7 Correct 495 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 526 ms 564 KB Output is correct
12 Correct 496 ms 568 KB Output is correct
13 Correct 585 ms 568 KB Output is correct
14 Correct 594 ms 528 KB Output is correct
15 Correct 44 ms 400 KB Output is correct
16 Correct 60 ms 528 KB Output is correct
17 Correct 127 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 400 KB Output is correct
2 Correct 770 ms 400 KB Output is correct
3 Correct 692 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 613 ms 400 KB Output is correct
8 Correct 896 ms 400 KB Output is correct
9 Correct 815 ms 400 KB Output is correct
10 Correct 656 ms 528 KB Output is correct
11 Correct 7 ms 476 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 4 ms 480 KB Output is correct
15 Correct 1 ms 476 KB Output is correct
16 Correct 642 ms 488 KB Output is correct
17 Correct 589 ms 488 KB Output is correct
18 Correct 570 ms 484 KB Output is correct
19 Correct 520 ms 484 KB Output is correct
20 Correct 600 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 484 KB Output is correct
2 Correct 488 ms 528 KB Output is correct
3 Correct 944 ms 400 KB Output is correct
4 Correct 747 ms 488 KB Output is correct
5 Correct 640 ms 520 KB Output is correct
6 Correct 466 ms 532 KB Output is correct
7 Correct 524 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 504 ms 468 KB Output is correct
12 Correct 629 ms 528 KB Output is correct
13 Correct 993 ms 480 KB Output is correct
14 Correct 711 ms 400 KB Output is correct
15 Correct 660 ms 528 KB Output is correct
16 Correct 435 ms 520 KB Output is correct
17 Correct 655 ms 404 KB Output is correct
18 Correct 481 ms 648 KB Output is correct
19 Correct 529 ms 528 KB Output is correct
20 Correct 519 ms 488 KB Output is correct
21 Correct 77 ms 400 KB Output is correct
22 Correct 77 ms 572 KB Output is correct
23 Correct 130 ms 552 KB Output is correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 6 ms 464 KB Output is correct
26 Correct 5 ms 480 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 536 ms 400 KB Output is correct
30 Correct 649 ms 400 KB Output is correct
31 Correct 657 ms 400 KB Output is correct
32 Correct 601 ms 428 KB Output is correct
33 Correct 605 ms 512 KB Output is correct
34 Correct 412 ms 528 KB Output is correct
35 Correct 503 ms 780 KB Output is correct
36 Correct 506 ms 528 KB Output is correct
37 Correct 518 ms 612 KB Output is correct
38 Correct 528 ms 588 KB Output is correct
39 Correct 491 ms 612 KB Output is correct
40 Correct 576 ms 648 KB Output is correct
41 Correct 599 ms 556 KB Output is correct
42 Correct 71 ms 556 KB Output is correct
43 Correct 102 ms 528 KB Output is correct
44 Correct 138 ms 532 KB Output is correct
45 Correct 205 ms 504 KB Output is correct
46 Correct 384 ms 656 KB Output is correct
47 Correct 366 ms 528 KB Output is correct
48 Correct 75 ms 580 KB Output is correct
49 Correct 70 ms 528 KB Output is correct