oj.uz

Submission #373633

# Submission time Handle Problem Language Result Execution time Memory
373633 2021-03-05T10:33:30 Z Jarif_Rahman Stations (IOI20_stations) C++17
10 / 100
 1126 ms 884 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){
    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 620 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 6 ms 620 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 3 ms 620 KB Invalid labels (values out of range). scenario=2, k=1000000, vertex=1, label=1006003
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 864 KB Output is correct
2 Correct 813 ms 868 KB Output is correct
3 Correct 803 ms 868 KB Output is correct
4 Correct 3 ms 756 KB Output is correct
5 Correct 5 ms 756 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 711 ms 736 KB Output is correct
8 Correct 1041 ms 868 KB Output is correct
9 Correct 734 ms 756 KB Output is correct
10 Correct 687 ms 868 KB Output is correct
11 Correct 6 ms 736 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 5 ms 736 KB Output is correct
14 Correct 4 ms 868 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 530 ms 884 KB Output is correct
17 Correct 509 ms 736 KB Output is correct
18 Correct 540 ms 736 KB Output is correct
19 Correct 514 ms 868 KB Output is correct
20 Correct 532 ms 884 KB Output is correct

Subtask #5
0 / 61.0

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