oj.uz

Submission #305916

# Submission time Handle Problem Language Result Execution time Memory
305916 2020-09-24T05:17:23 Z phathnv Stations (IOI20_stations) C++14
100 / 100
 1319 ms 1124 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int curInd, ind[N];
vector <int> adj[N];

void dfs(int u, int p, int c){
    if (!c)
        ind[u] = curInd++;

    for(int v : adj[u])
        if (v != p)
            dfs(v, u, c ^ 1);

    if (c)
        ind[u] = curInd++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    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]);
    }

    curInd = 0;
    dfs(0, -1, 0);
    return vector <int> (ind, ind + n);
}

int find_next_station(int s, int t, vector<int> c) {
    if ((int) c.size() == 1)
        return c.front();
    for(int v : c)
        if (v == t)
            return v;

    if (s < c.front()){
        int pre = s;
        for(int i = 0; i < (int) c.size(); i++){
            int nxt = c[i];
            assert(pre < nxt);
            if (pre < t && t <= nxt)
                return nxt;
            pre = nxt;
        }
        return c.back();
    } else {
        int pre = s;
        for(int i = (int) c.size() - 1; i > 0; i--){
            int nxt = c[i];
            assert(nxt < pre);
            if (nxt <= t && t < pre)
                return nxt;
            pre = nxt;
        }
        return c.front();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 1024 KB Output is correct
2 Correct 544 ms 1024 KB Output is correct
3 Correct 895 ms 768 KB Output is correct
4 Correct 600 ms 876 KB Output is correct
5 Correct 799 ms 876 KB Output is correct
6 Correct 432 ms 1024 KB Output is correct
7 Correct 492 ms 768 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 1 ms 884 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 832 KB Output is correct
2 Correct 694 ms 824 KB Output is correct
3 Correct 996 ms 768 KB Output is correct
4 Correct 843 ms 872 KB Output is correct
5 Correct 615 ms 768 KB Output is correct
6 Correct 530 ms 828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 1024 KB Output is correct
2 Correct 600 ms 1016 KB Output is correct
3 Correct 885 ms 872 KB Output is correct
4 Correct 699 ms 768 KB Output is correct
5 Correct 714 ms 872 KB Output is correct
6 Correct 484 ms 1024 KB Output is correct
7 Correct 532 ms 768 KB Output is correct
8 Correct 2 ms 880 KB Output is correct
9 Correct 5 ms 872 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 593 ms 876 KB Output is correct
12 Correct 472 ms 1008 KB Output is correct
13 Correct 591 ms 1008 KB Output is correct
14 Correct 429 ms 768 KB Output is correct
15 Correct 71 ms 868 KB Output is correct
16 Correct 70 ms 768 KB Output is correct
17 Correct 147 ms 816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 868 KB Output is correct
2 Correct 694 ms 876 KB Output is correct
3 Correct 892 ms 776 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 2 ms 880 KB Output is correct
7 Correct 750 ms 792 KB Output is correct
8 Correct 1319 ms 792 KB Output is correct
9 Correct 752 ms 768 KB Output is correct
10 Correct 623 ms 768 KB Output is correct
11 Correct 6 ms 872 KB Output is correct
12 Correct 6 ms 872 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 508 ms 768 KB Output is correct
17 Correct 506 ms 768 KB Output is correct
18 Correct 503 ms 768 KB Output is correct
19 Correct 651 ms 884 KB Output is correct
20 Correct 566 ms 876 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 1024 KB Output is correct
2 Correct 467 ms 1024 KB Output is correct
3 Correct 976 ms 768 KB Output is correct
4 Correct 729 ms 768 KB Output is correct
5 Correct 629 ms 768 KB Output is correct
6 Correct 552 ms 1124 KB Output is correct
7 Correct 437 ms 788 KB Output is correct
8 Correct 3 ms 1004 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 444 ms 768 KB Output is correct
12 Correct 646 ms 1048 KB Output is correct
13 Correct 1035 ms 872 KB Output is correct
14 Correct 736 ms 1024 KB Output is correct
15 Correct 718 ms 868 KB Output is correct
16 Correct 620 ms 824 KB Output is correct
17 Correct 666 ms 880 KB Output is correct
18 Correct 525 ms 772 KB Output is correct
19 Correct 599 ms 1024 KB Output is correct
20 Correct 509 ms 824 KB Output is correct
21 Correct 76 ms 876 KB Output is correct
22 Correct 70 ms 768 KB Output is correct
23 Correct 116 ms 804 KB Output is correct
24 Correct 6 ms 1008 KB Output is correct
25 Correct 5 ms 876 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 4 ms 876 KB Output is correct
28 Correct 2 ms 880 KB Output is correct
29 Correct 524 ms 872 KB Output is correct
30 Correct 512 ms 768 KB Output is correct
31 Correct 507 ms 884 KB Output is correct
32 Correct 508 ms 884 KB Output is correct
33 Correct 495 ms 880 KB Output is correct
34 Correct 319 ms 1024 KB Output is correct
35 Correct 457 ms 1024 KB Output is correct
36 Correct 472 ms 1024 KB Output is correct
37 Correct 449 ms 780 KB Output is correct
38 Correct 472 ms 768 KB Output is correct
39 Correct 429 ms 768 KB Output is correct
40 Correct 477 ms 768 KB Output is correct
41 Correct 479 ms 788 KB Output is correct
42 Correct 64 ms 824 KB Output is correct
43 Correct 112 ms 812 KB Output is correct
44 Correct 178 ms 796 KB Output is correct
45 Correct 173 ms 768 KB Output is correct
46 Correct 327 ms 1072 KB Output is correct
47 Correct 293 ms 784 KB Output is correct
48 Correct 68 ms 768 KB Output is correct
49 Correct 69 ms 1024 KB Output is correct