oj.uz

Submission #307446

# Submission time Handle Problem Language Result Execution time Memory
307446 2020-09-28T06:59:44 Z syy Stations (IOI20_stations) C++17
100 / 100
 1012 ms 1288 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss

int n, coun;
vi adj[1005], res;

// counting from 0
// Even row: smaller that all in subtree
// Odd row: greater than all in subtree
void dfs(int x, int p, bool dep) {
	if (!dep) res[x] = coun++;
	for (auto it:adj[x]) if (it != p) dfs(it, x, !dep);
	if (dep) res[x] = coun++;
}

vector<int> label(int N, int k, vector<int> u, vector<int> v) {
	n = N; res.clear(); res.resize(n);
	FOR(i, 0, n-1) adj[i].clear();
	coun = 0;
	FOR(i, 0, n-2) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
	int st = 0; FOR(i, 0, n-1) if (adj[i].size() == 1) st = i;
	dfs(st, -1, 0);
	return res;
}

int find_next_station(int s, int t, vector<int> c) {
	if (s < c[0]) { // Even row
		if (t < s or t >= c.back()) return c.back(); // must be out of subtree
		return *lower_bound(all(c), t); // lower_bound so children has space to "reduce" down to t
	} else { // Odd row
		if (t > s or t <= c[0]) return c[0]; // must be out of subtree
		return *(--upper_bound(all(c), t)); // upper_bound so children has space to "increase" up to t
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 1288 KB Output is correct
2 Correct 452 ms 1024 KB Output is correct
3 Correct 840 ms 1032 KB Output is correct
4 Correct 650 ms 872 KB Output is correct
5 Correct 586 ms 868 KB Output is correct
6 Correct 453 ms 1024 KB Output is correct
7 Correct 466 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 2 ms 1008 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 804 KB Output is correct
2 Correct 524 ms 816 KB Output is correct
3 Correct 859 ms 876 KB Output is correct
4 Correct 641 ms 872 KB Output is correct
5 Correct 608 ms 896 KB Output is correct
6 Correct 486 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 1024 KB Output is correct
2 Correct 481 ms 1024 KB Output is correct
3 Correct 1012 ms 868 KB Output is correct
4 Correct 627 ms 872 KB Output is correct
5 Correct 686 ms 768 KB Output is correct
6 Correct 442 ms 1024 KB Output is correct
7 Correct 443 ms 1024 KB Output is correct
8 Correct 3 ms 884 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 597 ms 880 KB Output is correct
12 Correct 590 ms 1024 KB Output is correct
13 Correct 592 ms 1108 KB Output is correct
14 Correct 504 ms 824 KB Output is correct
15 Correct 58 ms 864 KB Output is correct
16 Correct 67 ms 768 KB Output is correct
17 Correct 125 ms 812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 768 KB Output is correct
2 Correct 648 ms 872 KB Output is correct
3 Correct 636 ms 1048 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 708 ms 880 KB Output is correct
8 Correct 955 ms 1128 KB Output is correct
9 Correct 654 ms 768 KB Output is correct
10 Correct 589 ms 880 KB Output is correct
11 Correct 5 ms 872 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 5 ms 884 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 872 KB Output is correct
16 Correct 472 ms 768 KB Output is correct
17 Correct 518 ms 872 KB Output is correct
18 Correct 521 ms 876 KB Output is correct
19 Correct 504 ms 872 KB Output is correct
20 Correct 542 ms 872 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 1024 KB Output is correct
2 Correct 467 ms 1024 KB Output is correct
3 Correct 852 ms 872 KB Output is correct
4 Correct 662 ms 768 KB Output is correct
5 Correct 585 ms 876 KB Output is correct
6 Correct 456 ms 1128 KB Output is correct
7 Correct 452 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 880 KB Output is correct
11 Correct 449 ms 768 KB Output is correct
12 Correct 537 ms 816 KB Output is correct
13 Correct 853 ms 1032 KB Output is correct
14 Correct 644 ms 780 KB Output is correct
15 Correct 571 ms 864 KB Output is correct
16 Correct 445 ms 768 KB Output is correct
17 Correct 557 ms 868 KB Output is correct
18 Correct 473 ms 1112 KB Output is correct
19 Correct 486 ms 1024 KB Output is correct
20 Correct 443 ms 856 KB Output is correct
21 Correct 57 ms 768 KB Output is correct
22 Correct 76 ms 768 KB Output is correct
23 Correct 117 ms 1024 KB Output is correct
24 Correct 6 ms 884 KB Output is correct
25 Correct 6 ms 768 KB Output is correct
26 Correct 5 ms 868 KB Output is correct
27 Correct 4 ms 768 KB Output is correct
28 Correct 3 ms 960 KB Output is correct
29 Correct 510 ms 768 KB Output is correct
30 Correct 537 ms 872 KB Output is correct
31 Correct 529 ms 868 KB Output is correct
32 Correct 506 ms 1032 KB Output is correct
33 Correct 492 ms 864 KB Output is correct
34 Correct 312 ms 1124 KB Output is correct
35 Correct 432 ms 1008 KB Output is correct
36 Correct 443 ms 1024 KB Output is correct
37 Correct 450 ms 768 KB Output is correct
38 Correct 453 ms 768 KB Output is correct
39 Correct 433 ms 896 KB Output is correct
40 Correct 468 ms 768 KB Output is correct
41 Correct 459 ms 1144 KB Output is correct
42 Correct 63 ms 828 KB Output is correct
43 Correct 98 ms 940 KB Output is correct
44 Correct 130 ms 788 KB Output is correct
45 Correct 170 ms 768 KB Output is correct
46 Correct 312 ms 768 KB Output is correct
47 Correct 352 ms 776 KB Output is correct
48 Correct 68 ms 776 KB Output is correct
49 Correct 64 ms 1024 KB Output is correct