oj.uz

Submission #1090633

# Submission time Handle Problem Language Result Execution time Memory
1090633 2024-09-18T14:38:33 Z onlk97 Stations (IOI20_stations) C++14
0 / 100
 604 ms 1048 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector <int> g[1010];
int in[1010],out[1010],dep[1010],tme;
void dfs(int cur,int prv){
    if (prv==-1) dep[cur]=0;
    else dep[cur]=dep[prv]+1;
    in[cur]=++tme;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs(i,cur);
    }
    out[cur]=++tme;
}
vector <int> label(int n,int k,vector <int> u,vector <int> v){
    for (int i=0; i<n; i++) g[i].clear();
    tme=-1;
    for (int i=0; i<n-1; i++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0,-1);
    vector <int> ret(n);
    for (int i=0; i<n; i++){
        if (dep[i]%2==0) ret[i]=in[i];
        else ret[i]=out[i];
    }
    return ret;
}

int find_next_station(int s,int t,vector <int> c){
    if (c.size()==1) return c[0];
    if (binary_search(c.begin(),c.end(),t)) return t;
    if (s>*max_element(c.begin(),c.end())){
        for (int i=1; i+1<c.size(); i++){
            if (c[i]<=t&&t<c[i+1]) return c[i];
        }
        if (t>s||t<c[1]) return c.front();
        return c.back();
    }
    if (!s){
        for (int i=0; i<c.size(); i++){
            if (t<=c[i]) return c[i];
        }
    }
    for (int i=1; i+1<c.size(); i++){
        if (c[i-1]<t&&t<=c[i]) return c[i];
    }
    if (t<s||t>=c.back()) return c.back();
    return c.front();
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 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 2 ms 344 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 Correct 375 ms 684 KB Output is correct
2 Correct 323 ms 684 KB Output is correct
3 Correct 581 ms 680 KB Output is correct
4 Correct 453 ms 688 KB Output is correct
5 Correct 397 ms 688 KB Output is correct
6 Correct 296 ms 684 KB Output is correct
7 Correct 284 ms 684 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 1 ms 772 KB Output is correct
10 Correct 1 ms 772 KB Output is correct
11 Correct 430 ms 804 KB Output is correct
12 Correct 354 ms 1048 KB Output is correct
13 Incorrect 311 ms 796 KB Wrong query response.
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 684 KB Output is correct
2 Correct 468 ms 684 KB Output is correct
3 Correct 394 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 1 ms 764 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 377 ms 684 KB Output is correct
8 Correct 604 ms 684 KB Output is correct
9 Correct 453 ms 684 KB Output is correct
10 Correct 405 ms 684 KB Output is correct
11 Incorrect 3 ms 776 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 390 ms 684 KB Partially correct
2 Partially correct 319 ms 684 KB Partially correct
3 Correct 601 ms 684 KB Output is correct
4 Correct 445 ms 684 KB Output is correct
5 Correct 384 ms 684 KB Output is correct
6 Partially correct 286 ms 684 KB Partially correct
7 Partially correct 280 ms 684 KB Partially correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Incorrect 299 ms 684 KB Wrong query response.
12 Halted 0 ms 0 KB -