oj.uz

Submission #424359

# Submission time Handle Problem Language Result Execution time Memory
424359 2021-06-11T20:13:22 Z OttoTheDino Stations (IOI20_stations) C++17
100 / 100
 1140 ms 928 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e)                          for (int i = s; i <= e; ++i)
#define pb                                  push_back
typedef vector<int> vi;

const int mxn = 2e3;
int id, res[mxn];
vi neibs[mxn];

void dfs (int u, int prev, int d) {
    if (d%2) res[u]=id++;
    for (int v : neibs[u]) {
        if (v==prev) continue;
        dfs (v, u, d+1);
    }
    if (d%2==0) res[u]=id++;
}

vi label (int n, int k, vi u, vi v) {
    rep (i,0,n-2) {
        neibs[u[i]].pb(v[i]);
        neibs[v[i]].pb(u[i]);
    }
    dfs (0,-1,1);
    vi L(n);
    rep (i,0,n-1) L[i] = res[i];

    rep (i,0,n-1) neibs[i].clear();
    id = 0;

    return L;
}

int find_next_station (int s, int t, vi c) {
    sort(c.begin(), c.end());
    if (s < c.front()) {
        if (t<s) return c.back();
        for (int v : c) if (t<=v) return v;
        return c.back();
    }
    else {
        reverse(c.begin(), c.end());
        if (t>s) return c.back();
        for (int v : c) if (t>=v) return v;
        return c.back();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 920 KB Output is correct
2 Correct 529 ms 784 KB Output is correct
3 Correct 1015 ms 656 KB Output is correct
4 Correct 847 ms 792 KB Output is correct
5 Correct 742 ms 668 KB Output is correct
6 Correct 555 ms 772 KB Output is correct
7 Correct 476 ms 656 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 2 ms 720 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 656 KB Output is correct
2 Correct 654 ms 656 KB Output is correct
3 Correct 1009 ms 656 KB Output is correct
4 Correct 861 ms 660 KB Output is correct
5 Correct 691 ms 792 KB Output is correct
6 Correct 488 ms 660 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 784 KB Output is correct
2 Correct 616 ms 852 KB Output is correct
3 Correct 959 ms 656 KB Output is correct
4 Correct 724 ms 656 KB Output is correct
5 Correct 647 ms 784 KB Output is correct
6 Correct 510 ms 784 KB Output is correct
7 Correct 501 ms 660 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 4 ms 728 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 712 ms 656 KB Output is correct
12 Correct 460 ms 784 KB Output is correct
13 Correct 517 ms 784 KB Output is correct
14 Correct 523 ms 668 KB Output is correct
15 Correct 70 ms 656 KB Output is correct
16 Correct 81 ms 656 KB Output is correct
17 Correct 108 ms 664 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 656 KB Output is correct
2 Correct 780 ms 784 KB Output is correct
3 Correct 650 ms 664 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 1 ms 728 KB Output is correct
7 Correct 750 ms 656 KB Output is correct
8 Correct 1059 ms 656 KB Output is correct
9 Correct 838 ms 656 KB Output is correct
10 Correct 769 ms 656 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 588 ms 668 KB Output is correct
17 Correct 610 ms 656 KB Output is correct
18 Correct 570 ms 656 KB Output is correct
19 Correct 589 ms 656 KB Output is correct
20 Correct 576 ms 656 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 840 KB Output is correct
2 Correct 443 ms 784 KB Output is correct
3 Correct 1087 ms 656 KB Output is correct
4 Correct 716 ms 656 KB Output is correct
5 Correct 681 ms 664 KB Output is correct
6 Correct 557 ms 928 KB Output is correct
7 Correct 579 ms 660 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 1 ms 732 KB Output is correct
11 Correct 599 ms 672 KB Output is correct
12 Correct 633 ms 656 KB Output is correct
13 Correct 1140 ms 656 KB Output is correct
14 Correct 867 ms 664 KB Output is correct
15 Correct 563 ms 736 KB Output is correct
16 Correct 454 ms 660 KB Output is correct
17 Correct 689 ms 656 KB Output is correct
18 Correct 540 ms 660 KB Output is correct
19 Correct 467 ms 780 KB Output is correct
20 Correct 588 ms 656 KB Output is correct
21 Correct 55 ms 724 KB Output is correct
22 Correct 80 ms 680 KB Output is correct
23 Correct 109 ms 656 KB Output is correct
24 Correct 7 ms 724 KB Output is correct
25 Correct 9 ms 724 KB Output is correct
26 Correct 6 ms 724 KB Output is correct
27 Correct 4 ms 720 KB Output is correct
28 Correct 2 ms 724 KB Output is correct
29 Correct 570 ms 656 KB Output is correct
30 Correct 676 ms 672 KB Output is correct
31 Correct 522 ms 660 KB Output is correct
32 Correct 627 ms 656 KB Output is correct
33 Correct 508 ms 660 KB Output is correct
34 Correct 393 ms 784 KB Output is correct
35 Correct 438 ms 784 KB Output is correct
36 Correct 590 ms 788 KB Output is correct
37 Correct 511 ms 748 KB Output is correct
38 Correct 554 ms 656 KB Output is correct
39 Correct 450 ms 664 KB Output is correct
40 Correct 532 ms 664 KB Output is correct
41 Correct 553 ms 784 KB Output is correct
42 Correct 68 ms 656 KB Output is correct
43 Correct 128 ms 696 KB Output is correct
44 Correct 160 ms 656 KB Output is correct
45 Correct 197 ms 656 KB Output is correct
46 Correct 355 ms 656 KB Output is correct
47 Correct 395 ms 656 KB Output is correct
48 Correct 69 ms 676 KB Output is correct
49 Correct 93 ms 684 KB Output is correct