oj.uz

Submission #373635

# Submission time Handle Problem Language Result Execution time Memory
373635 2021-03-05T10:36:50 Z Jarif_Rahman Stations (IOI20_stations) C++17
10 / 100
 1103 ms 1012 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){
        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;
    }
    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 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 Incorrect 543 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 926 ms 756 KB Output is correct
2 Correct 785 ms 736 KB Output is correct
3 Correct 622 ms 996 KB Output is correct
4 Correct 3 ms 756 KB Output is correct
5 Correct 5 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 647 ms 736 KB Output is correct
8 Correct 1103 ms 1012 KB Output is correct
9 Correct 760 ms 756 KB Output is correct
10 Correct 624 ms 868 KB Output is correct
11 Correct 4 ms 756 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 7 ms 736 KB Output is correct
14 Correct 4 ms 736 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 718 ms 736 KB Output is correct
17 Correct 534 ms 768 KB Output is correct
18 Correct 517 ms 756 KB Output is correct
19 Correct 577 ms 868 KB Output is correct
20 Correct 601 ms 736 KB Output is correct

Subtask #5
0 / 61.0

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