oj.uz

Submission #617973

# Submission time Handle Problem Language Result Execution time Memory
617973 2022-08-01T18:29:17 Z someone Stations (IOI20_stations) C++14
100 / 100
 999 ms 1392 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 42;

int id, lab[N];
vector<int> adj[N];

void DFS(int i, int pre, bool preorder) {
    if(preorder)
        lab[i] = id++;
    for(int j : adj[i])
        if(j != pre)
            DFS(j, i, !preorder);
    if(!preorder)
        lab[i] = id++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    id = 0;
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 0; i < n-1; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    DFS(0, 0, true);
    vector<int> labels(n);
    for(int i = 0; i < n; i++)
        labels[i] = lab[i];
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int n = c.size();
    c.push_back(s);
    sort(c.begin(), c.end());
    if(c[0] == s) {
        if(t < c[0] || c[n-1] < t)
            return c[n];
        for(int i = n-1; i >= 0; i--)
            if(t > c[i])
                return c[i+1];
    } else if(c[n] == s) {
        if(t < c[1] || c[n] < t)
            return c[0];
        for(int i = 2; i <= n; i++)
            if(t < c[i])
                return c[i-1];
    }
    cout << "wtf";
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 1124 KB Output is correct
2 Correct 475 ms 1132 KB Output is correct
3 Correct 932 ms 996 KB Output is correct
4 Correct 711 ms 928 KB Output is correct
5 Correct 629 ms 1004 KB Output is correct
6 Correct 399 ms 1060 KB Output is correct
7 Correct 446 ms 1004 KB Output is correct
8 Correct 1 ms 1008 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 0 ms 1008 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 1060 KB Output is correct
2 Correct 549 ms 988 KB Output is correct
3 Correct 966 ms 1000 KB Output is correct
4 Correct 633 ms 928 KB Output is correct
5 Correct 645 ms 928 KB Output is correct
6 Correct 434 ms 1060 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1128 KB Output is correct
2 Correct 382 ms 1392 KB Output is correct
3 Correct 835 ms 928 KB Output is correct
4 Correct 634 ms 928 KB Output is correct
5 Correct 573 ms 1004 KB Output is correct
6 Correct 357 ms 1188 KB Output is correct
7 Correct 468 ms 1008 KB Output is correct
8 Correct 2 ms 1008 KB Output is correct
9 Correct 4 ms 1004 KB Output is correct
10 Correct 0 ms 1008 KB Output is correct
11 Correct 553 ms 996 KB Output is correct
12 Correct 499 ms 1196 KB Output is correct
13 Correct 399 ms 1192 KB Output is correct
14 Correct 497 ms 996 KB Output is correct
15 Correct 53 ms 1008 KB Output is correct
16 Correct 65 ms 964 KB Output is correct
17 Correct 105 ms 1056 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 988 KB Output is correct
2 Correct 581 ms 928 KB Output is correct
3 Correct 596 ms 996 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 4 ms 1008 KB Output is correct
6 Correct 1 ms 1016 KB Output is correct
7 Correct 473 ms 1076 KB Output is correct
8 Correct 846 ms 932 KB Output is correct
9 Correct 585 ms 1004 KB Output is correct
10 Correct 618 ms 928 KB Output is correct
11 Correct 5 ms 1020 KB Output is correct
12 Correct 3 ms 1008 KB Output is correct
13 Correct 4 ms 1008 KB Output is correct
14 Correct 3 ms 1004 KB Output is correct
15 Correct 2 ms 1008 KB Output is correct
16 Correct 511 ms 932 KB Output is correct
17 Correct 531 ms 932 KB Output is correct
18 Correct 528 ms 1068 KB Output is correct
19 Correct 525 ms 932 KB Output is correct
20 Correct 449 ms 932 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 1128 KB Output is correct
2 Correct 353 ms 1140 KB Output is correct
3 Correct 999 ms 928 KB Output is correct
4 Correct 688 ms 928 KB Output is correct
5 Correct 571 ms 996 KB Output is correct
6 Correct 485 ms 1124 KB Output is correct
7 Correct 419 ms 1056 KB Output is correct
8 Correct 2 ms 1012 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 2 ms 1008 KB Output is correct
11 Correct 476 ms 996 KB Output is correct
12 Correct 546 ms 1000 KB Output is correct
13 Correct 798 ms 928 KB Output is correct
14 Correct 579 ms 1000 KB Output is correct
15 Correct 561 ms 1000 KB Output is correct
16 Correct 467 ms 1060 KB Output is correct
17 Correct 644 ms 928 KB Output is correct
18 Correct 417 ms 1128 KB Output is correct
19 Correct 436 ms 1316 KB Output is correct
20 Correct 461 ms 1060 KB Output is correct
21 Correct 49 ms 1004 KB Output is correct
22 Correct 62 ms 956 KB Output is correct
23 Correct 116 ms 1116 KB Output is correct
24 Correct 4 ms 1008 KB Output is correct
25 Correct 6 ms 1008 KB Output is correct
26 Correct 4 ms 1016 KB Output is correct
27 Correct 3 ms 1008 KB Output is correct
28 Correct 1 ms 1008 KB Output is correct
29 Correct 555 ms 1000 KB Output is correct
30 Correct 525 ms 932 KB Output is correct
31 Correct 418 ms 928 KB Output is correct
32 Correct 425 ms 932 KB Output is correct
33 Correct 523 ms 1004 KB Output is correct
34 Correct 332 ms 992 KB Output is correct
35 Correct 437 ms 1124 KB Output is correct
36 Correct 476 ms 1128 KB Output is correct
37 Correct 369 ms 1256 KB Output is correct
38 Correct 392 ms 1068 KB Output is correct
39 Correct 491 ms 1248 KB Output is correct
40 Correct 508 ms 1084 KB Output is correct
41 Correct 427 ms 1196 KB Output is correct
42 Correct 52 ms 1216 KB Output is correct
43 Correct 99 ms 1060 KB Output is correct
44 Correct 120 ms 1056 KB Output is correct
45 Correct 148 ms 1004 KB Output is correct
46 Correct 303 ms 1004 KB Output is correct
47 Correct 333 ms 1000 KB Output is correct
48 Correct 70 ms 1152 KB Output is correct
49 Correct 56 ms 1000 KB Output is correct