oj.uz

Submission #361939

# Submission time Handle Problem Language Result Execution time Memory
361939 2021-02-01T09:57:40 Z valerikk Stations (IOI20_stations) C++14
10 / 100
 1010 ms 55732 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 17 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 605 ms 55648 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 47744 KB Output is correct
2 Correct 795 ms 47760 KB Output is correct
3 Correct 721 ms 47760 KB Output is correct
4 Correct 35 ms 47772 KB Output is correct
5 Correct 33 ms 47840 KB Output is correct
6 Correct 32 ms 47760 KB Output is correct
7 Correct 675 ms 47760 KB Output is correct
8 Correct 917 ms 47712 KB Output is correct
9 Correct 766 ms 47760 KB Output is correct
10 Correct 680 ms 47712 KB Output is correct
11 Correct 35 ms 47760 KB Output is correct
12 Correct 35 ms 47712 KB Output is correct
13 Correct 33 ms 47760 KB Output is correct
14 Correct 34 ms 47760 KB Output is correct
15 Correct 36 ms 47772 KB Output is correct
16 Correct 500 ms 47760 KB Output is correct
17 Correct 562 ms 47760 KB Output is correct
18 Correct 602 ms 47760 KB Output is correct
19 Correct 610 ms 47760 KB Output is correct
20 Correct 621 ms 47760 KB Output is correct

Subtask #5
0 / 61.0

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