oj.uz

Submission #781061

# Submission time Handle Problem Language Result Execution time Memory
781061 2023-07-12T16:45:44 Z kamelfanger83 Stations (IOI20_stations) C++14
52.3205 / 100
 762 ms 708 KB 
#include "stations.h"
#include <vector>
#include <cassert>

#define int long long

using namespace std;

vector<pair<int, int>> prepost;
vector<vector<int>> cons;
int C = 0;

void dfs(int i, int from){
    prepost[i].first = C++;
    for (int c : cons[i]){
        if (c == from) continue;
        dfs(c, i);
    }
    prepost[i].second = C - 1;
}

vector<signed> label(signed n, signed k, vector<signed> u, vector<signed> v) {
    vector<signed> labels(n);
    cons.clear();
    cons.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        cons[u[i]].push_back(v[i]);
        cons[v[i]].push_back(u[i]);
    }

    prepost.clear();
    prepost.resize(n);
    C = 0;
    dfs(0, -1);

    for (int i = 0; i < n; ++i) {
        labels[i] = prepost[i].first * 1000 + prepost[i].second;
    }

    return labels;
}

signed find_next_station(signed s, signed t, vector<signed> c) {
    int spre = s / 1000, spost = s % 1000;
    int tpre = t / 1000, tpost = t % 1000;
    bool isdes = spre < tpre && tpost <= spost;
    for (int i = 0; i < c.size(); ++i) {
        int cpre = c[i] / 1000, cpost = c[i] % 1000;
        if (cpre < spre && spost <= cpost){
            if (!isdes) return c[i];
        }
        else if (cpre <= tpre && tpost <= cpost){
            assert(isdes);
            return c[i];
        }
    }
    //assert(false);
    //return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 412 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 672 KB Output is correct
2 Correct 370 ms 620 KB Output is correct
3 Correct 657 ms 472 KB Output is correct
4 Correct 560 ms 416 KB Output is correct
5 Correct 542 ms 492 KB Output is correct
6 Correct 359 ms 544 KB Output is correct
7 Correct 319 ms 544 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 524 ms 492 KB Output is correct
12 Correct 402 ms 604 KB Output is correct
13 Correct 399 ms 544 KB Output is correct
14 Correct 333 ms 548 KB Output is correct
15 Correct 49 ms 496 KB Output is correct
16 Correct 60 ms 620 KB Output is correct
17 Correct 75 ms 520 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 420 KB Output is correct
2 Correct 576 ms 416 KB Output is correct
3 Correct 495 ms 416 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 533 ms 416 KB Output is correct
8 Correct 679 ms 420 KB Output is correct
9 Correct 600 ms 420 KB Output is correct
10 Correct 502 ms 492 KB Output is correct
11 Correct 4 ms 500 KB Output is correct
12 Correct 4 ms 500 KB Output is correct
13 Correct 2 ms 496 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 471 ms 492 KB Output is correct
17 Correct 492 ms 488 KB Output is correct
18 Correct 460 ms 416 KB Output is correct
19 Correct 378 ms 416 KB Output is correct
20 Correct 409 ms 492 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 463 ms 676 KB Partially correct
2 Partially correct 317 ms 552 KB Partially correct
3 Partially correct 746 ms 492 KB Partially correct
4 Partially correct 624 ms 416 KB Partially correct
5 Partially correct 532 ms 492 KB Partially correct
6 Partially correct 394 ms 616 KB Partially correct
7 Partially correct 329 ms 548 KB Partially correct
8 Partially correct 1 ms 500 KB Partially correct
9 Partially correct 2 ms 504 KB Partially correct
10 Partially correct 0 ms 488 KB Partially correct
11 Partially correct 421 ms 648 KB Partially correct
12 Partially correct 471 ms 544 KB Partially correct
13 Partially correct 635 ms 416 KB Partially correct
14 Partially correct 450 ms 420 KB Partially correct
15 Partially correct 469 ms 496 KB Partially correct
16 Partially correct 378 ms 544 KB Partially correct
17 Partially correct 539 ms 416 KB Partially correct
18 Partially correct 334 ms 616 KB Partially correct
19 Partially correct 421 ms 684 KB Partially correct
20 Partially correct 297 ms 544 KB Partially correct
21 Partially correct 41 ms 448 KB Partially correct
22 Partially correct 42 ms 620 KB Partially correct
23 Partially correct 91 ms 620 KB Partially correct
24 Partially correct 3 ms 496 KB Partially correct
25 Partially correct 4 ms 492 KB Partially correct
26 Partially correct 2 ms 492 KB Partially correct
27 Partially correct 1 ms 492 KB Partially correct
28 Partially correct 1 ms 492 KB Partially correct
29 Partially correct 347 ms 492 KB Partially correct
30 Partially correct 378 ms 496 KB Partially correct
31 Partially correct 398 ms 544 KB Partially correct
32 Partially correct 442 ms 420 KB Partially correct
33 Partially correct 356 ms 492 KB Partially correct
34 Partially correct 286 ms 548 KB Partially correct
35 Partially correct 289 ms 620 KB Partially correct
36 Partially correct 314 ms 692 KB Partially correct
37 Partially correct 353 ms 692 KB Partially correct
38 Partially correct 351 ms 612 KB Partially correct
39 Partially correct 412 ms 636 KB Partially correct
40 Partially correct 322 ms 692 KB Partially correct
41 Partially correct 376 ms 624 KB Partially correct
42 Partially correct 50 ms 620 KB Partially correct
43 Partially correct 69 ms 492 KB Partially correct
44 Partially correct 92 ms 548 KB Partially correct
45 Partially correct 131 ms 544 KB Partially correct
46 Partially correct 292 ms 544 KB Partially correct
47 Partially correct 227 ms 544 KB Partially correct
48 Partially correct 47 ms 600 KB Partially correct
49 Partially correct 48 ms 708 KB Partially correct