oj.uz

Submission #1099553

# Submission time Handle Problem Language Result Execution time Memory
1099553 2024-10-11T15:24:51 Z Tymond Stations (IOI20_stations) C++17
100 / 100
 628 ms 1040 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

vi col;
int timer = 0;
vector<vi> g;

void dfs(int v, int p, int f){
    if(f == 0){
        col[v] = timer++;
    }

    for(auto u : g[v]){
        if(u == p){
            continue;
        }
        dfs(u, v, 1 - f);
    }

    if(f){
        col[v] = timer++;
    }
}

vi label(int n, int k, vi u, vi v){
    k++;
    col.assign(n, 0);
    g.resize(n);
    for(int i = 0; i < n; i++){
        g[i].clear();
    }
    timer = 0;
    for(int i = 0; i < n - 1; i++){
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }

    dfs(0, 0, 0);
    return col;
}

int find_next_station(int s, int t, vi c){
    sort(all(c));
    if(sz(c) == 1){
        return c[0];
    }

    if(s == 0){
        for(auto ele : c){
            if(t <= ele){
                return ele;
            }
        }
        return c.back();
    }

    int cnt[2] = {0, 0};
    for(auto ele : c){
        if(ele < s){
            cnt[1]++;
        }else{
            cnt[0]++;
        }
    }

    if(cnt[0] > cnt[1]){
        //fs = 0
        for(int i = 0; i + 1 < sz(c); i++){
            if(t >= s && t <= c[i]){
                return c[i];
            }
        }
        return c.back();
    }else{
        //fs = 1
        for(int i = sz(c) - 1; i > 0; i--){
            if(t >= c[i] && t <= s){
                return c[i];
            }
        }
        return c[0];
    }
}
 
/*int main(){
    vi c = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
    for(int i = 0; i < 5; i++){
        cout << c[i] << ' ';
    }
    cout << '\n';
    cout << find_next_station(c[2], c[0], {c[1], c[4]}) << '\n';
 
    return 0;
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 684 KB Output is correct
2 Correct 296 ms 940 KB Output is correct
3 Correct 628 ms 684 KB Output is correct
4 Correct 446 ms 684 KB Output is correct
5 Correct 406 ms 684 KB Output is correct
6 Correct 286 ms 684 KB Output is correct
7 Correct 296 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 684 KB Output is correct
2 Correct 337 ms 684 KB Output is correct
3 Correct 579 ms 696 KB Output is correct
4 Correct 444 ms 684 KB Output is correct
5 Correct 431 ms 684 KB Output is correct
6 Correct 319 ms 688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 944 KB Output is correct
2 Correct 317 ms 936 KB Output is correct
3 Correct 619 ms 684 KB Output is correct
4 Correct 454 ms 684 KB Output is correct
5 Correct 407 ms 684 KB Output is correct
6 Correct 308 ms 684 KB Output is correct
7 Correct 283 ms 936 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 0 ms 764 KB Output is correct
11 Correct 374 ms 684 KB Output is correct
12 Correct 310 ms 768 KB Output is correct
13 Correct 339 ms 936 KB Output is correct
14 Correct 329 ms 684 KB Output is correct
15 Correct 26 ms 764 KB Output is correct
16 Correct 44 ms 768 KB Output is correct
17 Correct 79 ms 760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 684 KB Output is correct
2 Correct 459 ms 684 KB Output is correct
3 Correct 450 ms 684 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 357 ms 688 KB Output is correct
8 Correct 608 ms 684 KB Output is correct
9 Correct 470 ms 944 KB Output is correct
10 Correct 379 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 776 KB Output is correct
15 Correct 0 ms 776 KB Output is correct
16 Correct 308 ms 684 KB Output is correct
17 Correct 331 ms 684 KB Output is correct
18 Correct 340 ms 684 KB Output is correct
19 Correct 351 ms 684 KB Output is correct
20 Correct 347 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 940 KB Output is correct
2 Correct 322 ms 940 KB Output is correct
3 Correct 562 ms 688 KB Output is correct
4 Correct 433 ms 684 KB Output is correct
5 Correct 393 ms 684 KB Output is correct
6 Correct 314 ms 684 KB Output is correct
7 Correct 313 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 776 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 287 ms 684 KB Output is correct
12 Correct 363 ms 684 KB Output is correct
13 Correct 578 ms 684 KB Output is correct
14 Correct 436 ms 684 KB Output is correct
15 Correct 366 ms 684 KB Output is correct
16 Correct 295 ms 684 KB Output is correct
17 Correct 425 ms 684 KB Output is correct
18 Correct 310 ms 688 KB Output is correct
19 Correct 312 ms 932 KB Output is correct
20 Correct 297 ms 684 KB Output is correct
21 Correct 33 ms 704 KB Output is correct
22 Correct 44 ms 764 KB Output is correct
23 Correct 67 ms 684 KB Output is correct
24 Correct 3 ms 764 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 ms 776 KB Output is correct
28 Correct 1 ms 776 KB Output is correct
29 Correct 348 ms 712 KB Output is correct
30 Correct 373 ms 684 KB Output is correct
31 Correct 403 ms 684 KB Output is correct
32 Correct 354 ms 684 KB Output is correct
33 Correct 350 ms 684 KB Output is correct
34 Correct 190 ms 684 KB Output is correct
35 Correct 293 ms 940 KB Output is correct
36 Correct 298 ms 1020 KB Output is correct
37 Correct 310 ms 788 KB Output is correct
38 Correct 328 ms 932 KB Output is correct
39 Correct 303 ms 1040 KB Output is correct
40 Correct 294 ms 1028 KB Output is correct
41 Correct 300 ms 772 KB Output is correct
42 Correct 37 ms 684 KB Output is correct
43 Correct 59 ms 744 KB Output is correct
44 Correct 89 ms 768 KB Output is correct
45 Correct 103 ms 684 KB Output is correct
46 Correct 193 ms 684 KB Output is correct
47 Correct 227 ms 684 KB Output is correct
48 Correct 39 ms 772 KB Output is correct
49 Correct 42 ms 952 KB Output is correct