oj.uz

Submission #350406

# Submission time Handle Problem Language Result Execution time Memory
350406 2021-01-19T05:31:14 Z talant117408 Stations (IOI20_stations) C++17
100 / 100
 1166 ms 1168 KB 
#include "stations.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "stub.cpp"
#endif
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

vector <vector <int>> graph(1003);
int timer, tin[1003], tout[1003];

void dfs(int v, int p, int type){
    if(type) tout[v] = ++timer;
    for(auto to : graph[v]){
        if(to != p){
            dfs(to, v, 1-type);
        }
    }
    if(!type) tout[v] = ++timer;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
    timer = 0;
    for(int i = 0; i < n; i++){
        graph[i].clear();
    }
    vector <int> labels(n);
    for(int i = 0; i < sz(u); i++){
        graph[u[i]].pb(v[i]);
        graph[v[i]].pb(u[i]);
    }
    dfs(0, 0, 0);
    for(int i = 0; i < n; i++){
        labels[i] = tout[i];
    }
    return labels;
}

int find_next_station(int s, int t, vector<int> c){
    if(s > c.back()){
        if(t < c[0] || s < t) return c[0];
        auto it = ub(all(c), t);
        return *(--it);
    }
    else{
        if(c.back() < t || t < s) return c.back();
        auto it = lb(all(c), t);
        return *it;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 1088 KB Output is correct
2 Correct 473 ms 864 KB Output is correct
3 Correct 1166 ms 864 KB Output is correct
4 Correct 750 ms 736 KB Output is correct
5 Correct 600 ms 948 KB Output is correct
6 Correct 660 ms 864 KB Output is correct
7 Correct 542 ms 1112 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 4 ms 864 KB Output is correct
10 Correct 2 ms 948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 1044 KB Output is correct
2 Correct 630 ms 900 KB Output is correct
3 Correct 929 ms 736 KB Output is correct
4 Correct 718 ms 1024 KB Output is correct
5 Correct 603 ms 956 KB Output is correct
6 Correct 488 ms 904 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 992 KB Output is correct
2 Correct 514 ms 992 KB Output is correct
3 Correct 1009 ms 864 KB Output is correct
4 Correct 683 ms 884 KB Output is correct
5 Correct 613 ms 864 KB Output is correct
6 Correct 503 ms 992 KB Output is correct
7 Correct 507 ms 900 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 568 ms 948 KB Output is correct
12 Correct 460 ms 968 KB Output is correct
13 Correct 466 ms 992 KB Output is correct
14 Correct 596 ms 884 KB Output is correct
15 Correct 66 ms 864 KB Output is correct
16 Correct 75 ms 736 KB Output is correct
17 Correct 124 ms 816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 900 KB Output is correct
2 Correct 812 ms 864 KB Output is correct
3 Correct 826 ms 884 KB Output is correct
4 Correct 16 ms 864 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 9 ms 864 KB Output is correct
7 Correct 590 ms 992 KB Output is correct
8 Correct 785 ms 736 KB Output is correct
9 Correct 881 ms 864 KB Output is correct
10 Correct 600 ms 864 KB Output is correct
11 Correct 5 ms 948 KB Output is correct
12 Correct 6 ms 864 KB Output is correct
13 Correct 6 ms 736 KB Output is correct
14 Correct 5 ms 996 KB Output is correct
15 Correct 2 ms 956 KB Output is correct
16 Correct 707 ms 736 KB Output is correct
17 Correct 492 ms 948 KB Output is correct
18 Correct 514 ms 864 KB Output is correct
19 Correct 734 ms 864 KB Output is correct
20 Correct 620 ms 992 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 900 KB Output is correct
2 Correct 645 ms 1012 KB Output is correct
3 Correct 1067 ms 736 KB Output is correct
4 Correct 750 ms 864 KB Output is correct
5 Correct 678 ms 864 KB Output is correct
6 Correct 636 ms 1168 KB Output is correct
7 Correct 503 ms 864 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 6 ms 864 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 618 ms 1144 KB Output is correct
12 Correct 708 ms 864 KB Output is correct
13 Correct 1115 ms 900 KB Output is correct
14 Correct 704 ms 948 KB Output is correct
15 Correct 714 ms 948 KB Output is correct
16 Correct 555 ms 900 KB Output is correct
17 Correct 693 ms 736 KB Output is correct
18 Correct 446 ms 992 KB Output is correct
19 Correct 479 ms 1120 KB Output is correct
20 Correct 486 ms 864 KB Output is correct
21 Correct 51 ms 736 KB Output is correct
22 Correct 66 ms 884 KB Output is correct
23 Correct 112 ms 876 KB Output is correct
24 Correct 5 ms 948 KB Output is correct
25 Correct 5 ms 864 KB Output is correct
26 Correct 5 ms 848 KB Output is correct
27 Correct 4 ms 736 KB Output is correct
28 Correct 2 ms 736 KB Output is correct
29 Correct 667 ms 736 KB Output is correct
30 Correct 521 ms 864 KB Output is correct
31 Correct 606 ms 864 KB Output is correct
32 Correct 619 ms 800 KB Output is correct
33 Correct 643 ms 864 KB Output is correct
34 Correct 357 ms 896 KB Output is correct
35 Correct 414 ms 1012 KB Output is correct
36 Correct 534 ms 992 KB Output is correct
37 Correct 513 ms 1008 KB Output is correct
38 Correct 468 ms 1164 KB Output is correct
39 Correct 531 ms 1120 KB Output is correct
40 Correct 432 ms 944 KB Output is correct
41 Correct 547 ms 1012 KB Output is correct
42 Correct 84 ms 892 KB Output is correct
43 Correct 130 ms 992 KB Output is correct
44 Correct 161 ms 992 KB Output is correct
45 Correct 160 ms 1000 KB Output is correct
46 Correct 297 ms 736 KB Output is correct
47 Correct 310 ms 864 KB Output is correct
48 Correct 61 ms 1108 KB Output is correct
49 Correct 61 ms 1092 KB Output is correct