oj.uz

Submission #362045

# Submission time Handle Problem Language Result Execution time Memory
362045 2021-02-01T16:12:16 Z valerikk Stations (IOI20_stations) C++17
0 / 100
 1146 ms 1024 KB 
#include <bits/stdc++.h>
using namespace std; 

const int N = 1007;
vector<int> g[N];
int a[N], b[N], C, dep[N];

void dfs(int v,int d = 0, int p =-1){
    a[v] = C++;
    dep[v] = d;
    for(int u : g[v]){
        if (u!= p) {
            dfs(u, d + 1, v);
        }
    }
    b[v] = C++;
}

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]);
    }
    C = 0;
    dfs(0);
    vector<int> L(n);
    for(int i =0 ; i < n ; i++) L[i] = (dep[i]&1) ? b[i] : a[i];
    return L;
}

int find_next_station(int s, int t, vector<int> c) {
    for (int v : c) {
        if (v == t) return v;
    }
    bool f = 1;
    for (int v : c) f &= v > s;
    if (f) {
        int lst = s;
        for (int i = 0; i < c.size(); i++) {
            if (i == (int)c.size() - 1) return c[i];
            if (t > lst && t < c[i]) return c[i];
            lst = c[i];
        }
        assert(0);
        return -1;
    }
    int lst = s;
    for (int i = (int)c.size() - 2; i >= 0; i--){
        if (t < lst && t > c[i]) return c[i];
        lst = c[i];
    }
    return c[(int)c.size() - 1];
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < c.size(); i++) {
      |                         ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1146 ms 828 KB Output is correct
2 Correct 696 ms 1024 KB Output is correct
3 Incorrect 651 ms 940 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

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