oj.uz

Submission #420001

# Submission time Handle Problem Language Result Execution time Memory
420001 2021-06-07T21:35:36 Z NintsiChkhaidze Stations (IOI20_stations) C++14
10 / 100
 991 ms 600 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector <int> vec[1005];
int cnt = -1,in[1005],out[1005];
bool q=0;
void dfs(int x,int p){
    in[x] = ++cnt;
    for (int j=0;j<vec[x].size();j++){
        int to = vec[x][j];
        if (to == p) continue;
        dfs(to,x);
    }
    out[x] = cnt;
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<int> labels;
    for (int i=0;i<1001;i++){
        vec[i].clear();
        in[i] = out[i] = 0;
    }
    for (int i=0;i<u.size();i++){
        vec[u[i]].pb(v[i]);
        vec[v[i]].pb(u[i]);
    }
    
    cnt=0;
    dfs(0,0);
    for (int i=0;i<n;i++)
        labels.pb(in[i]*1000 + out[i]);
    
    return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    int Ins = (s/1000),Int = (t/1000),Out = (t%1000);
    if (Ins < Int){
        for (int i=1;i<c.size();i++)
            if (Int >= (c[i]/1000) && (c[i]%1000) >= Out) return c[i];
    }
    return c[0];
}

Compilation message

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int j=0;j<vec[x].size();j++){
      |                  ~^~~~~~~~~~~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0;i<u.size();i++){
      |                  ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i=1;i<c.size();i++)
      |                      ~^~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 496 KB Output is correct
2 Correct 741 ms 400 KB Output is correct
3 Correct 757 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 701 ms 528 KB Output is correct
8 Correct 974 ms 520 KB Output is correct
9 Correct 905 ms 400 KB Output is correct
10 Correct 751 ms 516 KB Output is correct
11 Correct 5 ms 544 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 603 ms 528 KB Output is correct
17 Correct 676 ms 528 KB Output is correct
18 Correct 671 ms 400 KB Output is correct
19 Correct 721 ms 512 KB Output is correct
20 Correct 576 ms 400 KB Output is correct

Subtask #5
0 / 61.0

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