oj.uz

Submission #410899

# Submission time Handle Problem Language Result Execution time Memory
410899 2021-05-23T21:50:28 Z 534351 Stations (IOI20_stations) C++17
100 / 100
 1128 ms 876 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

const int MAXN = 1013;
const int INF = 1e9 + 7;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K, T;
vi edge[MAXN];
int st[MAXN], ft[MAXN], depth[MAXN];
vi ans;
//inside each vtx, we store start time and finish time.

void dfs(int u, int p)
{
    if (depth[u] % 2 == 0)
    {
        st[u] = T;
        ans[u] = st[u];
        T++;
    }
	for (int v : edge[u])
	{
		if (v == p) continue;
        depth[v] = depth[u] + 1;
		dfs(v, u);
	}
    if (depth[u] % 2 == 1)
    {
        ft[u] = T;
        ans[u] = ft[u];
        T++;
    }
}

vi label(int n, int k, vi U, vi V)
{
	N = n; K = k; T = 0;
	FOR(i, 0, N)
	{
		edge[i].clear();
	}
    ans.resize(N);
	FOR(i, 0, N - 1)
	{
		int u = U[i], v = V[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
    depth[0] = 0;
	dfs(0, N);
	return ans;
}

int find_next_station(int u, int v, vi ch)
{
    sort(ALL(ch));
    //figure out if you're a st or ft.
    //case 1: you're an st. then any neighbor will have ft > u.
    if (u < ch[0])
    {
        int ft = -1;
        //you're an st. your ft is the second largest neighbor unless you are the root, and then it's the largest + 1.
        if (u == 0)
        {
            ft = ch.back() + 1;
        }
        else
        {
            ft = (SZ(ch) > 1 ? ch[SZ(ch) - 2] : u) + 1;
        }
        if (u <= v && v <= ft)
        {
            //you're going to an ft, which still is >= v.
            FOR(i, 0, SZ(ch))
            {
                if (ch[i] >= v) return ch[i];
            }
        }
        else
        {
            return ch.back();
        }
    }
    else
    {
        //you're an ft. your st is the smallest child - 1, unless you only have a parent.
        int st = -1;
        if (SZ(ch) == 1)
        {
            st = ch[0] + 1;
        }
        else
        {
            st = ch[0] - 1;
        }
        if (st <= v && v <= u)
        {
            //you're going to an st, which is <= v.
            FORD(i, SZ(ch), 0)
            {
                if (ch[i] <= v) return ch[i];
            }
        }
        else
        {
            return ch[0];
        }
    }
    return ch[0];
    // assert(false);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 672 KB Output is correct
2 Correct 515 ms 640 KB Output is correct
3 Correct 926 ms 400 KB Output is correct
4 Correct 733 ms 528 KB Output is correct
5 Correct 814 ms 400 KB Output is correct
6 Correct 581 ms 660 KB Output is correct
7 Correct 462 ms 512 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 492 KB Output is correct
2 Correct 525 ms 512 KB Output is correct
3 Correct 906 ms 504 KB Output is correct
4 Correct 634 ms 400 KB Output is correct
5 Correct 709 ms 512 KB Output is correct
6 Correct 574 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 640 KB Output is correct
2 Correct 520 ms 516 KB Output is correct
3 Correct 1065 ms 400 KB Output is correct
4 Correct 924 ms 528 KB Output is correct
5 Correct 737 ms 400 KB Output is correct
6 Correct 606 ms 528 KB Output is correct
7 Correct 541 ms 528 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 786 ms 516 KB Output is correct
12 Correct 451 ms 876 KB Output is correct
13 Correct 528 ms 768 KB Output is correct
14 Correct 528 ms 516 KB Output is correct
15 Correct 55 ms 552 KB Output is correct
16 Correct 71 ms 548 KB Output is correct
17 Correct 120 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 400 KB Output is correct
2 Correct 669 ms 656 KB Output is correct
3 Correct 773 ms 528 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 755 ms 528 KB Output is correct
8 Correct 1128 ms 528 KB Output is correct
9 Correct 794 ms 528 KB Output is correct
10 Correct 672 ms 528 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 543 ms 768 KB Output is correct
17 Correct 605 ms 516 KB Output is correct
18 Correct 699 ms 528 KB Output is correct
19 Correct 681 ms 400 KB Output is correct
20 Correct 661 ms 528 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 656 KB Output is correct
2 Correct 531 ms 528 KB Output is correct
3 Correct 1075 ms 400 KB Output is correct
4 Correct 741 ms 512 KB Output is correct
5 Correct 760 ms 400 KB Output is correct
6 Correct 539 ms 528 KB Output is correct
7 Correct 503 ms 640 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 528 ms 636 KB Output is correct
12 Correct 668 ms 504 KB Output is correct
13 Correct 962 ms 504 KB Output is correct
14 Correct 627 ms 400 KB Output is correct
15 Correct 790 ms 528 KB Output is correct
16 Correct 484 ms 512 KB Output is correct
17 Correct 741 ms 400 KB Output is correct
18 Correct 458 ms 512 KB Output is correct
19 Correct 451 ms 528 KB Output is correct
20 Correct 430 ms 544 KB Output is correct
21 Correct 74 ms 608 KB Output is correct
22 Correct 62 ms 576 KB Output is correct
23 Correct 113 ms 656 KB Output is correct
24 Correct 7 ms 596 KB Output is correct
25 Correct 5 ms 596 KB Output is correct
26 Correct 6 ms 596 KB Output is correct
27 Correct 5 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 714 ms 508 KB Output is correct
30 Correct 468 ms 528 KB Output is correct
31 Correct 677 ms 512 KB Output is correct
32 Correct 570 ms 528 KB Output is correct
33 Correct 680 ms 528 KB Output is correct
34 Correct 387 ms 528 KB Output is correct
35 Correct 507 ms 660 KB Output is correct
36 Correct 455 ms 804 KB Output is correct
37 Correct 460 ms 624 KB Output is correct
38 Correct 530 ms 776 KB Output is correct
39 Correct 480 ms 636 KB Output is correct
40 Correct 577 ms 528 KB Output is correct
41 Correct 439 ms 636 KB Output is correct
42 Correct 84 ms 656 KB Output is correct
43 Correct 113 ms 656 KB Output is correct
44 Correct 180 ms 608 KB Output is correct
45 Correct 160 ms 528 KB Output is correct
46 Correct 319 ms 528 KB Output is correct
47 Correct 420 ms 532 KB Output is correct
48 Correct 82 ms 688 KB Output is correct
49 Correct 77 ms 704 KB Output is correct