oj.uz

Submission #373648

# Submission time Handle Problem Language Result Execution time Memory
373648 2021-03-05T11:20:55 Z Jarif_Rahman Stations (IOI20_stations) C++17
10 / 100
 1136 ms 1296 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<vector<int>> v;
vector<int> lb, sz;
pair<int, int> div(int x){
    int a = x/1000, b = x%1000;
    if(b == 0) b = 1000;
    return make_pair(a, b);
}
int in = 0;
void dfs(int nd, int ss){
    lb[nd] = 1000*in;
    in++;
    for(int x: v[nd]) if(x!=ss) dfs(x, nd);
    for(int x: v[nd]) if(x!=ss) sz[nd]+=sz[x];
    lb[nd]+=sz[nd];
}
vector<int> label(int n, int k, vector<int> aa, vector<int> bb){
    in = 0;
    v.assign(n, {});
    lb.assign(n, -1);
    sz.assign(n, 1);
    for(int i = 0; i < n-1; i++){
        v[aa[i]].pb(bb[i]);
        v[bb[i]].pb(aa[i]);
    }
    dfs(0, -1);
    return lb;
}
int find_next_station(int s, int t, vector<int> c){
    auto [a, b] = div(s);
    auto [x, y] = div(t);
    if(x < a || x > a+b-1){
        for(int xx: c){
            auto [aa, bb] = div(xx);
            if(a >= aa && a <= aa+bb-1) return xx;
        }
    }
    for(int xx: c){
        auto [aa, bb] = div(xx);
        if(a >= aa && a <= aa+bb-1) continue;
        if(x >= aa && x <= aa+bb-1) return xx;
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 317 ms 1120 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 736 KB Output is correct
2 Correct 770 ms 736 KB Output is correct
3 Correct 717 ms 756 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 1 ms 756 KB Output is correct
7 Correct 593 ms 736 KB Output is correct
8 Correct 1031 ms 756 KB Output is correct
9 Correct 746 ms 884 KB Output is correct
10 Correct 783 ms 864 KB Output is correct
11 Correct 7 ms 736 KB Output is correct
12 Correct 6 ms 756 KB Output is correct
13 Correct 5 ms 756 KB Output is correct
14 Correct 4 ms 996 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 594 ms 756 KB Output is correct
17 Correct 600 ms 756 KB Output is correct
18 Correct 617 ms 756 KB Output is correct
19 Correct 641 ms 736 KB Output is correct
20 Correct 548 ms 756 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 1296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -