oj.uz

Submission #373641

# Submission time Handle Problem Language Result Execution time Memory
373641 2021-03-05T10:52:12 Z Jarif_Rahman Stations (IOI20_stations) C++17
10 / 100
 943 ms 1120 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){
    return make_pair(x/1000, x%1000);
}
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:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 492 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 381 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 918 ms 736 KB Output is correct
2 Correct 720 ms 864 KB Output is correct
3 Correct 609 ms 876 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 621 ms 756 KB Output is correct
8 Correct 943 ms 868 KB Output is correct
9 Correct 667 ms 868 KB Output is correct
10 Correct 683 ms 756 KB Output is correct
11 Correct 7 ms 756 KB Output is correct
12 Correct 7 ms 736 KB Output is correct
13 Correct 5 ms 736 KB Output is correct
14 Correct 5 ms 756 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 526 ms 860 KB Output is correct
17 Correct 532 ms 756 KB Output is correct
18 Correct 633 ms 884 KB Output is correct
19 Correct 605 ms 756 KB Output is correct
20 Correct 519 ms 868 KB Output is correct

Subtask #5
0 / 61.0

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