oj.uz

Submission #306151

# Submission time Handle Problem Language Result Execution time Memory
306151 2020-09-24T16:49:53 Z SorahISA Stations (IOI20_stations) C++17
52.3205 / 100
 968 ms 1032 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

const int maxn = 1000 + 5;

vector<int> adj[maxn], lab, sz;
int tok = 0;

void dfs(int now, int lst) {
    lab[now] = tok++, sz[now] = 1;
    for (auto x : adj[now]) {
        if (x != lst) dfs(x, now), sz[now] += sz[x];
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i = 0; i < maxn; ++i) adj[i].clear();
    lab.resize(n), sz.resize(n);
    tok = 0;
    
    for (int i = 0; i < n-1; ++i) {
        adj[u[i]].eb(v[i]), adj[v[i]].eb(u[i]);
    }
    dfs(0, -1);
    
    for (int i = 0; i < n; ++i) lab[i] += sz[i] * 1000;
    
    // cout << "lab : ";
    // for (int i = 0; i < n; ++i) cout << lab[i] << " \n"[i == n-1];
    
    return lab;
}

int find_next_station(int s, int t, vector<int> c) {
    sort(ALL(c), [](auto a, auto b) {return a%1000 < b%1000;});
    // cout << "c : "; for (auto x : c) cout << x << " "; cout << "\n";
    if (s%1000 > t%1000 or s%1000 + s/1000 <= t%1000) return c[0];
    for (int i = 1; i < c.size(); ++i) {
        if (c[i]%1000 > t%1000) return c[i - 1];
    }
    return c.back();
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 1016 KB Output is correct
2 Correct 481 ms 1024 KB Output is correct
3 Correct 968 ms 1008 KB Output is correct
4 Correct 685 ms 892 KB Output is correct
5 Correct 639 ms 768 KB Output is correct
6 Correct 451 ms 1024 KB Output is correct
7 Correct 537 ms 776 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 632 ms 880 KB Output is correct
12 Correct 534 ms 1008 KB Output is correct
13 Correct 593 ms 1008 KB Output is correct
14 Correct 495 ms 816 KB Output is correct
15 Correct 65 ms 872 KB Output is correct
16 Correct 96 ms 952 KB Output is correct
17 Correct 149 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 880 KB Output is correct
2 Correct 668 ms 768 KB Output is correct
3 Correct 626 ms 876 KB Output is correct
4 Correct 3 ms 928 KB Output is correct
5 Correct 6 ms 880 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 758 ms 792 KB Output is correct
8 Correct 944 ms 856 KB Output is correct
9 Correct 793 ms 880 KB Output is correct
10 Correct 585 ms 1032 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 4 ms 1004 KB Output is correct
14 Correct 4 ms 884 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 575 ms 768 KB Output is correct
17 Correct 619 ms 768 KB Output is correct
18 Correct 544 ms 1024 KB Output is correct
19 Correct 547 ms 1024 KB Output is correct
20 Correct 554 ms 876 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 605 ms 1024 KB Partially correct
2 Partially correct 597 ms 1008 KB Partially correct
3 Partially correct 912 ms 768 KB Partially correct
4 Partially correct 802 ms 880 KB Partially correct
5 Partially correct 710 ms 768 KB Partially correct
6 Partially correct 465 ms 1024 KB Partially correct
7 Partially correct 517 ms 788 KB Partially correct
8 Partially correct 3 ms 768 KB Partially correct
9 Partially correct 6 ms 768 KB Partially correct
10 Partially correct 2 ms 896 KB Partially correct
11 Partially correct 505 ms 768 KB Partially correct
12 Partially correct 612 ms 828 KB Partially correct
13 Partially correct 957 ms 776 KB Partially correct
14 Partially correct 668 ms 876 KB Partially correct
15 Partially correct 629 ms 876 KB Partially correct
16 Partially correct 451 ms 824 KB Partially correct
17 Partially correct 655 ms 876 KB Partially correct
18 Partially correct 470 ms 780 KB Partially correct
19 Partially correct 472 ms 1024 KB Partially correct
20 Partially correct 466 ms 824 KB Partially correct
21 Partially correct 84 ms 872 KB Partially correct
22 Partially correct 101 ms 836 KB Partially correct
23 Partially correct 157 ms 812 KB Partially correct
24 Partially correct 7 ms 780 KB Partially correct
25 Partially correct 6 ms 880 KB Partially correct
26 Partially correct 4 ms 884 KB Partially correct
27 Partially correct 4 ms 768 KB Partially correct
28 Partially correct 1 ms 1008 KB Partially correct
29 Partially correct 616 ms 768 KB Partially correct
30 Partially correct 542 ms 768 KB Partially correct
31 Partially correct 517 ms 768 KB Partially correct
32 Partially correct 563 ms 768 KB Partially correct
33 Partially correct 608 ms 872 KB Partially correct
34 Partially correct 370 ms 1024 KB Partially correct
35 Partially correct 459 ms 1024 KB Partially correct
36 Partially correct 458 ms 1024 KB Partially correct
37 Partially correct 475 ms 768 KB Partially correct
38 Partially correct 443 ms 780 KB Partially correct
39 Partially correct 434 ms 768 KB Partially correct
40 Partially correct 454 ms 772 KB Partially correct
41 Partially correct 502 ms 904 KB Partially correct
42 Partially correct 78 ms 768 KB Partially correct
43 Partially correct 152 ms 804 KB Partially correct
44 Partially correct 157 ms 968 KB Partially correct
45 Partially correct 159 ms 768 KB Partially correct
46 Partially correct 327 ms 776 KB Partially correct
47 Partially correct 413 ms 788 KB Partially correct
48 Partially correct 72 ms 776 KB Partially correct
49 Partially correct 73 ms 1024 KB Partially correct