oj.uz

Submission #362021

# Submission time Handle Problem Language Result Execution time Memory
362021 2021-02-01T14:48:27 Z valerikk Stations (IOI20_stations) C++17
10 / 100
 1037 ms 1340 KB 
#include <bits/stdc++.h>

using namespace std; 

const int N = 1000;
vector<int> g[N];
int t = 0;
vector<int> l;

int dfs(int v, int p = -1) {
    l[v] = t++;
    int mx = l[v];
    for (int u : g[v]) {
        if (u != p) mx = max(mx, dfs(u, v));
    }
    l[v] *= N;
    l[v] += mx;
    return mx;
}

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

int find_next_station(int s, int t, vector<int> c) {
    int p = -1;
    for (int v : c) {
        if (v / N <= s / N && s / N <= v % N) p = v; else {
            if (v / N <= t / N && t / N <= v % N) return v;
        } 
    }
    assert(~p);
    return p;
}

#ifdef LOCAL
int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif 
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 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 364 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 864 KB Output is correct
2 Correct 693 ms 864 KB Output is correct
3 Correct 671 ms 864 KB Output is correct
4 Correct 3 ms 952 KB Output is correct
5 Correct 6 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 653 ms 1120 KB Output is correct
8 Correct 1013 ms 952 KB Output is correct
9 Correct 760 ms 736 KB Output is correct
10 Correct 680 ms 952 KB Output is correct
11 Correct 5 ms 736 KB Output is correct
12 Correct 6 ms 960 KB Output is correct
13 Correct 6 ms 864 KB Output is correct
14 Correct 4 ms 864 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 613 ms 952 KB Output is correct
17 Correct 541 ms 864 KB Output is correct
18 Correct 515 ms 1024 KB Output is correct
19 Correct 545 ms 992 KB Output is correct
20 Correct 584 ms 864 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -