oj.uz

Submission #312409

# Submission time Handle Problem Language Result Execution time Memory
312409 2020-10-13T06:21:15 Z jainbot27 Stations (IOI20_stations) C++17
100 / 100
 989 ms 1128 KB 
#include <bits/stdc++.h>
// #include "stations.h"
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 1001;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

vi label(int N, int K, vi U, vi V){
    vector<vi> adj(N);
    F0R(i, N-1){
        adj[U[i]].pb(V[i]);
        adj[V[i]].pb(U[i]);
    }
    vi res(N); int idx = 0;
    function<void(int, int)> dfs;
    dfs = [&] (int u, int p){
        if(p == -1 || !res[p]) res[u] = ++idx;
        trav(v, adj[u]) if(v != p) dfs(v, u);
        if(!res[u]) res[u] = ++idx;
    };
    dfs(0, -1);
    return res;
}

int find_next_station(int s, int t, vi c){
    if(c.back() < s) reverse(all(c));
    trav(x, c) {
        if(min(s, x) <= t && t <= max(s, x)) return x;
    }
    return c.back();
}

// int main(){
//     int n, k; cin >> n >> k;
//     vi U, V;
//     F0R(i, n-1){
//         int uu, vv; cin >> uu;
//         U.pb(uu);
//     }
//     F0R(i, n-1){
//         int uu, vv; cin >> vv;
//         V.pb(vv);
//     }

//     vi ANS = label(n, k, U, V);
//     F0R(i, n){
//         cout << ANS[i] << "\n";
//     }
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 1104 KB Output is correct
2 Correct 450 ms 1128 KB Output is correct
3 Correct 865 ms 640 KB Output is correct
4 Correct 733 ms 640 KB Output is correct
5 Correct 658 ms 640 KB Output is correct
6 Correct 508 ms 1024 KB Output is correct
7 Correct 440 ms 768 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 812 KB Output is correct
2 Correct 564 ms 820 KB Output is correct
3 Correct 951 ms 640 KB Output is correct
4 Correct 766 ms 640 KB Output is correct
5 Correct 603 ms 1040 KB Output is correct
6 Correct 536 ms 1088 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 1016 KB Output is correct
2 Correct 569 ms 1024 KB Output is correct
3 Correct 979 ms 640 KB Output is correct
4 Correct 685 ms 648 KB Output is correct
5 Correct 603 ms 644 KB Output is correct
6 Correct 470 ms 1024 KB Output is correct
7 Correct 442 ms 1024 KB Output is correct
8 Correct 3 ms 776 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 644 KB Output is correct
11 Correct 618 ms 640 KB Output is correct
12 Correct 487 ms 1124 KB Output is correct
13 Correct 471 ms 1124 KB Output is correct
14 Correct 559 ms 832 KB Output is correct
15 Correct 55 ms 888 KB Output is correct
16 Correct 67 ms 852 KB Output is correct
17 Correct 123 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 640 KB Output is correct
2 Correct 800 ms 784 KB Output is correct
3 Correct 677 ms 640 KB Output is correct
4 Correct 3 ms 652 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 1 ms 892 KB Output is correct
7 Correct 598 ms 640 KB Output is correct
8 Correct 898 ms 640 KB Output is correct
9 Correct 776 ms 640 KB Output is correct
10 Correct 744 ms 640 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 7 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Correct 482 ms 768 KB Output is correct
17 Correct 556 ms 652 KB Output is correct
18 Correct 540 ms 640 KB Output is correct
19 Correct 617 ms 640 KB Output is correct
20 Correct 549 ms 640 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 1024 KB Output is correct
2 Correct 502 ms 1008 KB Output is correct
3 Correct 908 ms 640 KB Output is correct
4 Correct 680 ms 768 KB Output is correct
5 Correct 650 ms 768 KB Output is correct
6 Correct 494 ms 1024 KB Output is correct
7 Correct 549 ms 768 KB Output is correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 5 ms 644 KB Output is correct
10 Correct 1 ms 648 KB Output is correct
11 Correct 481 ms 800 KB Output is correct
12 Correct 551 ms 824 KB Output is correct
13 Correct 957 ms 644 KB Output is correct
14 Correct 674 ms 640 KB Output is correct
15 Correct 581 ms 768 KB Output is correct
16 Correct 516 ms 820 KB Output is correct
17 Correct 720 ms 644 KB Output is correct
18 Correct 463 ms 1016 KB Output is correct
19 Correct 559 ms 1024 KB Output is correct
20 Correct 532 ms 824 KB Output is correct
21 Correct 62 ms 776 KB Output is correct
22 Correct 73 ms 908 KB Output is correct
23 Correct 114 ms 768 KB Output is correct
24 Correct 6 ms 648 KB Output is correct
25 Correct 5 ms 768 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 4 ms 652 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 551 ms 912 KB Output is correct
30 Correct 546 ms 768 KB Output is correct
31 Correct 505 ms 640 KB Output is correct
32 Correct 536 ms 640 KB Output is correct
33 Correct 508 ms 892 KB Output is correct
34 Correct 332 ms 776 KB Output is correct
35 Correct 442 ms 1008 KB Output is correct
36 Correct 456 ms 1024 KB Output is correct
37 Correct 452 ms 924 KB Output is correct
38 Correct 468 ms 804 KB Output is correct
39 Correct 474 ms 968 KB Output is correct
40 Correct 509 ms 796 KB Output is correct
41 Correct 534 ms 888 KB Output is correct
42 Correct 81 ms 828 KB Output is correct
43 Correct 140 ms 816 KB Output is correct
44 Correct 178 ms 824 KB Output is correct
45 Correct 169 ms 808 KB Output is correct
46 Correct 324 ms 768 KB Output is correct
47 Correct 375 ms 1024 KB Output is correct
48 Correct 66 ms 824 KB Output is correct
49 Correct 71 ms 768 KB Output is correct