oj.uz

Submission #373634

# Submission time Handle Problem Language Result Execution time Memory
373634 2021-03-05T10:34:53 Z Jarif_Rahman Stations (IOI20_stations) C++17
10 / 100
 1081 ms 1068 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){
    sort(c.begin(), c.end());
    auto [a, b] = div(s);
    auto [x, y] = div(t);
    if(x < a || x > a+b-1) return c.front();
    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;
    }
    return -1;
}

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 4 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 Incorrect 616 ms 864 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 756 KB Output is correct
2 Correct 828 ms 756 KB Output is correct
3 Correct 749 ms 1060 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 6 ms 868 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 731 ms 756 KB Output is correct
8 Correct 1002 ms 996 KB Output is correct
9 Correct 829 ms 1068 KB Output is correct
10 Correct 700 ms 996 KB Output is correct
11 Correct 6 ms 756 KB Output is correct
12 Correct 5 ms 868 KB Output is correct
13 Correct 5 ms 756 KB Output is correct
14 Correct 4 ms 756 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 603 ms 736 KB Output is correct
17 Correct 548 ms 848 KB Output is correct
18 Correct 534 ms 868 KB Output is correct
19 Correct 669 ms 884 KB Output is correct
20 Correct 621 ms 1060 KB Output is correct

Subtask #5
0 / 61.0

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