oj.uz

Submission #415668

# Submission time Handle Problem Language Result Execution time Memory
415668 2021-06-01T10:55:02 Z Odavey Stations (IOI20_stations) C++14
67.2269 / 100
 1128 ms 820 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            1005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

vector<int> adj[MX_N];
int glit = 0;
int in[MX_N], out[MX_N];
int p[MX_N];
int l[MX_N];

void fill(int at, int d){
    in[at] = glit++;
    for(int to : adj[at]){
        if(p[at] == to){
            continue;
        }
        p[to] = at;
        fill(to, d+1);
    }
    out[at] = glit++;
    l[at] = (d%2)?out[at]:in[at];
    return;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
    for(int i=0;i<n;++i){
        adj[i] = {};
    }
    for(int i=0;i<n-1;++i){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }
    fill(0, 0);
    vector<int> ans;
    for(int i=0;i<n;++i){
        ans.pb(l[i]);
    }
    return ans;
}

int find_next_station(int s, int t, vector<int> c){
    if(s < c.front()){
        if(t < s){
            return c.back();
        }else{
            int lo = 0;
            int hi = c.size()-1;
            while(lo < hi){
                int mid = lo + (hi-lo)/2;
                if(t <= c[mid]){
                    hi = mid;
                }else{
                    lo = mid+1;
                }
            }
            return c[lo];
        }
    }else{
        if(t > s){
            return c.front();
        }else{
            int lo = 0;
            int hi = c.size()-1;
            while(lo < hi){
                int mid = lo + (hi-lo+1)/2;
                if(t >= c[mid]){
                    lo = mid;
                }else{
                    hi = mid-1;
                }
            }
            return c[lo];
        }
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 668 KB Output is correct
2 Correct 520 ms 648 KB Output is correct
3 Correct 919 ms 512 KB Output is correct
4 Correct 817 ms 512 KB Output is correct
5 Correct 662 ms 680 KB Output is correct
6 Correct 649 ms 620 KB Output is correct
7 Correct 522 ms 556 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 722 ms 400 KB Output is correct
12 Correct 518 ms 748 KB Output is correct
13 Correct 471 ms 744 KB Output is correct
14 Correct 504 ms 520 KB Output is correct
15 Correct 68 ms 528 KB Output is correct
16 Correct 59 ms 528 KB Output is correct
17 Correct 161 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 520 KB Output is correct
2 Correct 944 ms 528 KB Output is correct
3 Correct 784 ms 512 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 790 ms 516 KB Output is correct
8 Correct 1128 ms 504 KB Output is correct
9 Correct 783 ms 520 KB Output is correct
10 Correct 587 ms 508 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 6 ms 596 KB Output is correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 533 ms 512 KB Output is correct
17 Correct 643 ms 528 KB Output is correct
18 Correct 644 ms 528 KB Output is correct
19 Correct 653 ms 604 KB Output is correct
20 Correct 633 ms 528 KB Output is correct

Subtask #5
41.2269 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 599 ms 644 KB Partially correct
2 Partially correct 550 ms 656 KB Partially correct
3 Correct 1081 ms 528 KB Output is correct
4 Correct 698 ms 528 KB Output is correct
5 Correct 736 ms 512 KB Output is correct
6 Partially correct 532 ms 636 KB Partially correct
7 Partially correct 679 ms 504 KB Partially correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Partially correct 591 ms 476 KB Partially correct
12 Partially correct 621 ms 528 KB Partially correct
13 Correct 1095 ms 500 KB Output is correct
14 Correct 759 ms 528 KB Output is correct
15 Correct 829 ms 512 KB Output is correct
16 Partially correct 543 ms 516 KB Partially correct
17 Correct 642 ms 512 KB Output is correct
18 Partially correct 644 ms 648 KB Partially correct
19 Partially correct 682 ms 748 KB Partially correct
20 Partially correct 552 ms 716 KB Partially correct
21 Partially correct 78 ms 576 KB Partially correct
22 Partially correct 103 ms 656 KB Partially correct
23 Partially correct 153 ms 656 KB Partially correct
24 Correct 11 ms 680 KB Output is correct
25 Correct 8 ms 648 KB Output is correct
26 Correct 7 ms 596 KB Output is correct
27 Correct 4 ms 596 KB Output is correct
28 Correct 3 ms 608 KB Output is correct
29 Correct 536 ms 528 KB Output is correct
30 Correct 633 ms 512 KB Output is correct
31 Correct 720 ms 528 KB Output is correct
32 Correct 572 ms 516 KB Output is correct
33 Correct 593 ms 404 KB Output is correct
34 Partially correct 408 ms 636 KB Partially correct
35 Partially correct 580 ms 652 KB Partially correct
36 Partially correct 468 ms 760 KB Partially correct
37 Partially correct 546 ms 648 KB Partially correct
38 Partially correct 593 ms 716 KB Partially correct
39 Partially correct 544 ms 752 KB Partially correct
40 Partially correct 534 ms 764 KB Partially correct
41 Partially correct 534 ms 632 KB Partially correct
42 Partially correct 90 ms 584 KB Partially correct
43 Partially correct 126 ms 656 KB Partially correct
44 Partially correct 132 ms 612 KB Partially correct
45 Partially correct 240 ms 528 KB Partially correct
46 Partially correct 457 ms 576 KB Partially correct
47 Partially correct 384 ms 520 KB Partially correct
48 Partially correct 88 ms 784 KB Partially correct
49 Partially correct 71 ms 820 KB Partially correct