oj.uz

Submission #308934

# Submission time Handle Problem Language Result Execution time Memory
308934 2020-10-02T10:25:21 Z Vimmer Stations (IOI20_stations) C++14
100 / 100
 1085 ms 10428 KB 
#include <bits/stdc++.h>
#include "stations.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define N 200005
#define PB push_back
#define sz(x) int(x.size())
#define F first
#define M ll(1e9 + 7)
#define S second
#define all(x) x.begin(), x.end()
#define endl '\n'

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
//typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll mlt(ll x, ll y) {return (x * y) % M;}
ll sm(ll x, ll y) {return (x + y) % M;}


vector <int> g[N], a;

int id = 0;

void dfs(int v, int p, int hr)
{
    if (hr % 2 == 0) a[v] = id++;

    for (auto it : g[v])
    {
        if (it == p) continue;

        dfs(it, v, hr + 1);
    }

    if (hr % 2) a[v] = id++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
    for (int i = 0; i < n; i++) g[i].clear();

    a.resize(n);

    id = 0;

    for (int i = 0; i < n - 1; i++)
    {
        g[u[i]].PB(v[i]);

        g[v[i]].PB(u[i]);
    }

    dfs(0, -1, 0);

    return a;
}

int find_next_station(int s, int t, vector<int> c)
{
    sort(all(c));

    if (c.back() < s)
    {
        if (t > s) return c[0];

        int i = 1;

        while (i < sz(c) && t >= c[i]) i++;

        if (i == 0) return c[0];

        return c[i - 1];
    }
    else
    {
        if (t < s) return c.back();

        int i = 0;

        while (i < sz(c) - 1 && t > c[i]) i++;

        return c[i];
    }
}

//int main()
//{
//    iostream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    //freopen("fcolor.in", "r", stdin); freopen("fcolor.out", "w", stdout);
//
//
//}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 10272 KB Output is correct
2 Correct 526 ms 10260 KB Output is correct
3 Correct 1070 ms 10152 KB Output is correct
4 Correct 670 ms 10160 KB Output is correct
5 Correct 638 ms 10144 KB Output is correct
6 Correct 460 ms 10292 KB Output is correct
7 Correct 502 ms 10240 KB Output is correct
8 Correct 11 ms 10152 KB Output is correct
9 Correct 12 ms 10164 KB Output is correct
10 Correct 8 ms 9984 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 10240 KB Output is correct
2 Correct 657 ms 10232 KB Output is correct
3 Correct 1085 ms 10156 KB Output is correct
4 Correct 654 ms 10152 KB Output is correct
5 Correct 650 ms 10300 KB Output is correct
6 Correct 470 ms 10240 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 10260 KB Output is correct
2 Correct 504 ms 10272 KB Output is correct
3 Correct 845 ms 10296 KB Output is correct
4 Correct 668 ms 10280 KB Output is correct
5 Correct 580 ms 10160 KB Output is correct
6 Correct 517 ms 10272 KB Output is correct
7 Correct 502 ms 10428 KB Output is correct
8 Correct 9 ms 9984 KB Output is correct
9 Correct 10 ms 10284 KB Output is correct
10 Correct 8 ms 10148 KB Output is correct
11 Correct 574 ms 10156 KB Output is correct
12 Correct 479 ms 10388 KB Output is correct
13 Correct 524 ms 10284 KB Output is correct
14 Correct 511 ms 10224 KB Output is correct
15 Correct 64 ms 10144 KB Output is correct
16 Correct 80 ms 10124 KB Output is correct
17 Correct 134 ms 10340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 10160 KB Output is correct
2 Correct 675 ms 10160 KB Output is correct
3 Correct 739 ms 10224 KB Output is correct
4 Correct 10 ms 10112 KB Output is correct
5 Correct 10 ms 10152 KB Output is correct
6 Correct 8 ms 10152 KB Output is correct
7 Correct 624 ms 9984 KB Output is correct
8 Correct 901 ms 9984 KB Output is correct
9 Correct 765 ms 10152 KB Output is correct
10 Correct 762 ms 10156 KB Output is correct
11 Correct 13 ms 10112 KB Output is correct
12 Correct 12 ms 10156 KB Output is correct
13 Correct 11 ms 10112 KB Output is correct
14 Correct 10 ms 10148 KB Output is correct
15 Correct 8 ms 10112 KB Output is correct
16 Correct 630 ms 10184 KB Output is correct
17 Correct 579 ms 9984 KB Output is correct
18 Correct 577 ms 10156 KB Output is correct
19 Correct 619 ms 10156 KB Output is correct
20 Correct 511 ms 10152 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 10268 KB Output is correct
2 Correct 445 ms 10276 KB Output is correct
3 Correct 925 ms 10112 KB Output is correct
4 Correct 661 ms 10112 KB Output is correct
5 Correct 593 ms 10288 KB Output is correct
6 Correct 484 ms 10276 KB Output is correct
7 Correct 437 ms 10232 KB Output is correct
8 Correct 9 ms 10160 KB Output is correct
9 Correct 10 ms 10240 KB Output is correct
10 Correct 8 ms 10148 KB Output is correct
11 Correct 467 ms 10384 KB Output is correct
12 Correct 526 ms 10348 KB Output is correct
13 Correct 911 ms 10152 KB Output is correct
14 Correct 672 ms 10152 KB Output is correct
15 Correct 579 ms 9984 KB Output is correct
16 Correct 519 ms 10252 KB Output is correct
17 Correct 647 ms 9984 KB Output is correct
18 Correct 534 ms 10428 KB Output is correct
19 Correct 473 ms 10400 KB Output is correct
20 Correct 449 ms 10368 KB Output is correct
21 Correct 62 ms 10112 KB Output is correct
22 Correct 105 ms 10240 KB Output is correct
23 Correct 123 ms 10344 KB Output is correct
24 Correct 14 ms 10156 KB Output is correct
25 Correct 13 ms 10160 KB Output is correct
26 Correct 11 ms 10148 KB Output is correct
27 Correct 10 ms 10152 KB Output is correct
28 Correct 9 ms 10368 KB Output is correct
29 Correct 563 ms 10148 KB Output is correct
30 Correct 561 ms 10112 KB Output is correct
31 Correct 591 ms 10124 KB Output is correct
32 Correct 682 ms 9984 KB Output is correct
33 Correct 535 ms 10156 KB Output is correct
34 Correct 360 ms 10352 KB Output is correct
35 Correct 477 ms 10376 KB Output is correct
36 Correct 538 ms 10288 KB Output is correct
37 Correct 531 ms 10304 KB Output is correct
38 Correct 571 ms 10236 KB Output is correct
39 Correct 604 ms 10304 KB Output is correct
40 Correct 490 ms 10344 KB Output is correct
41 Correct 589 ms 10176 KB Output is correct
42 Correct 72 ms 10240 KB Output is correct
43 Correct 149 ms 10188 KB Output is correct
44 Correct 183 ms 10224 KB Output is correct
45 Correct 201 ms 10240 KB Output is correct
46 Correct 413 ms 10348 KB Output is correct
47 Correct 326 ms 10316 KB Output is correct
48 Correct 65 ms 10240 KB Output is correct
49 Correct 66 ms 10240 KB Output is correct