oj.uz

Submission #362018

# Submission time Handle Problem Language Result Execution time Memory
362018 2021-02-01T14:47:46 Z valerikk Stations (IOI20_stations) C++17
10 / 100
 1014 ms 55660 KB 
#include <vector>
using namespace std;

const int N = 1e6 + 7;
vector<int> g[N];
int tin[N], tout[N], t;

void dfs(int v, int p = -1) {
    tin[v] = t++;
    for (int u : g[v]) {
        if (u != p) dfs(u, v);
    }
    tout[v] = t;
}

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]);
    }
    t = 0;
    dfs(0);
    tout[0] = n - 1;
    vector<int> l(n);
    for (int i = 0; i < n; i++) l[i] = tin[i]*1000 + tout[i];
    return l;
}

void f(int v) {
    tin[v] = v / 1000;
    tout[v] = v % 1000;
    if (tin[v] == 0) tout[v]++;
}

int find_next_station(int s, int t, vector<int> c) {
    f(s); f(t);
    for (int v : c) f(v);
    int p;
    for (int v : c) {
        if (tin[v] <= tin[s] && tout[v] >= tout[s]) {
            p = v;
            continue;
        }
        if (tin[v] <= tin[t] && tout[v] >= tout[t]) return v;
    }
    return p;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:39:9: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int p;
      |         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23916 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6010
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23916 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1512
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 696 ms 55660 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 47760 KB Output is correct
2 Correct 702 ms 47760 KB Output is correct
3 Correct 722 ms 47920 KB Output is correct
4 Correct 34 ms 47712 KB Output is correct
5 Correct 36 ms 47712 KB Output is correct
6 Correct 33 ms 47712 KB Output is correct
7 Correct 711 ms 47760 KB Output is correct
8 Correct 1014 ms 47732 KB Output is correct
9 Correct 679 ms 47712 KB Output is correct
10 Correct 878 ms 47712 KB Output is correct
11 Correct 36 ms 47712 KB Output is correct
12 Correct 37 ms 47760 KB Output is correct
13 Correct 36 ms 47896 KB Output is correct
14 Correct 34 ms 47760 KB Output is correct
15 Correct 33 ms 47824 KB Output is correct
16 Correct 641 ms 47696 KB Output is correct
17 Correct 601 ms 47760 KB Output is correct
18 Correct 575 ms 47712 KB Output is correct
19 Correct 680 ms 47968 KB Output is correct
20 Correct 625 ms 47712 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 645 ms 55648 KB Wrong query response.
2 Halted 0 ms 0 KB -