oj.uz

Submission #306140

# Submission time Handle Problem Language Result Execution time Memory
306140 2020-09-24T16:08:37 Z SorahISA Stations (IOI20_stations) C++17
52.3205 / 100
 1109 ms 1140 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 672 ms 1008 KB Output is correct
2 Correct 469 ms 1024 KB Output is correct
3 Correct 1109 ms 880 KB Output is correct
4 Correct 770 ms 768 KB Output is correct
5 Correct 684 ms 768 KB Output is correct
6 Correct 544 ms 1008 KB Output is correct
7 Correct 475 ms 788 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 656 ms 768 KB Output is correct
12 Correct 535 ms 1024 KB Output is correct
13 Correct 492 ms 1112 KB Output is correct
14 Correct 516 ms 824 KB Output is correct
15 Correct 65 ms 880 KB Output is correct
16 Correct 97 ms 840 KB Output is correct
17 Correct 122 ms 812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1009 ms 896 KB Output is correct
2 Correct 774 ms 1032 KB Output is correct
3 Correct 597 ms 880 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 5 ms 888 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 671 ms 768 KB Output is correct
8 Correct 1027 ms 880 KB Output is correct
9 Correct 759 ms 896 KB Output is correct
10 Correct 661 ms 876 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 7 ms 880 KB Output is correct
13 Correct 5 ms 880 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 2 ms 896 KB Output is correct
16 Correct 572 ms 880 KB Output is correct
17 Correct 629 ms 1008 KB Output is correct
18 Correct 513 ms 884 KB Output is correct
19 Correct 498 ms 768 KB Output is correct
20 Correct 531 ms 872 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 644 ms 1008 KB Partially correct
2 Partially correct 492 ms 1024 KB Partially correct
3 Partially correct 987 ms 876 KB Partially correct
4 Partially correct 779 ms 876 KB Partially correct
5 Partially correct 609 ms 888 KB Partially correct
6 Partially correct 538 ms 1048 KB Partially correct
7 Partially correct 527 ms 796 KB Partially correct
8 Partially correct 3 ms 768 KB Partially correct
9 Partially correct 5 ms 1008 KB Partially correct
10 Partially correct 2 ms 880 KB Partially correct
11 Partially correct 498 ms 792 KB Partially correct
12 Partially correct 635 ms 812 KB Partially correct
13 Partially correct 941 ms 872 KB Partially correct
14 Partially correct 690 ms 768 KB Partially correct
15 Partially correct 636 ms 768 KB Partially correct
16 Partially correct 502 ms 820 KB Partially correct
17 Partially correct 717 ms 768 KB Partially correct
18 Partially correct 522 ms 888 KB Partially correct
19 Partially correct 562 ms 1024 KB Partially correct
20 Partially correct 509 ms 768 KB Partially correct
21 Partially correct 67 ms 768 KB Partially correct
22 Partially correct 87 ms 844 KB Partially correct
23 Partially correct 151 ms 812 KB Partially correct
24 Partially correct 6 ms 876 KB Partially correct
25 Partially correct 7 ms 768 KB Partially correct
26 Partially correct 5 ms 888 KB Partially correct
27 Partially correct 4 ms 768 KB Partially correct
28 Partially correct 2 ms 768 KB Partially correct
29 Partially correct 622 ms 768 KB Partially correct
30 Partially correct 697 ms 1024 KB Partially correct
31 Partially correct 540 ms 768 KB Partially correct
32 Partially correct 668 ms 768 KB Partially correct
33 Partially correct 797 ms 876 KB Partially correct
34 Partially correct 349 ms 1140 KB Partially correct
35 Partially correct 530 ms 1120 KB Partially correct
36 Partially correct 504 ms 1108 KB Partially correct
37 Partially correct 548 ms 768 KB Partially correct
38 Partially correct 569 ms 768 KB Partially correct
39 Partially correct 469 ms 768 KB Partially correct
40 Partially correct 540 ms 1008 KB Partially correct
41 Partially correct 469 ms 900 KB Partially correct
42 Partially correct 75 ms 1024 KB Partially correct
43 Partially correct 134 ms 812 KB Partially correct
44 Partially correct 154 ms 784 KB Partially correct
45 Partially correct 212 ms 912 KB Partially correct
46 Partially correct 401 ms 780 KB Partially correct
47 Partially correct 434 ms 784 KB Partially correct
48 Partially correct 88 ms 768 KB Partially correct
49 Partially correct 79 ms 1024 KB Partially correct