oj.uz

Submission #639631

# Submission time Handle Problem Language Result Execution time Memory
639631 2022-09-10T18:47:02 Z ghostwriter Stations (IOI20_stations) C++14
100 / 100
 946 ms 916 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "stub.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int MAXN = 1e3 + 5;
int N, tin[MAXN], tout[MAXN], l[MAXN], cnt = 0;
vi adj[MAXN];
void dfs(int u, int p, int h) {
	tin[u] = cnt++;
	EACH(v, adj[u]) {
		if (v == p) continue;
		dfs(v, u, h ^ 1);
	}
	tout[u] = cnt++;
	if (h & 1) l[u] = tout[u];
	else l[u] = tin[u];
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	N = n;
	FOR(i, 0, N - 1) adj[i].clear();
	FOR(i, 0, N - 2) {
		int ui = u[i], vi = v[i];
		adj[ui].pb(vi);
		adj[vi].pb(ui);
	}
	dfs(0, -1, 0);
	vi b;
	FOR(i, 0, N - 1) b.pb(l[i]);
	sort(all(b));
	FOR(i, 0, N - 1) l[i] = lb(all(b), l[i]) - b.begin();
	vi l1;
	FOR(i, 0, N - 1) l1.pb(l[i]);
	return l1;
}
int find_next_station(int s, int t, std::vector<int> c) {
	if (s < c[0]) {
		if (t > c[sz(c) - 2]) return c[sz(c) - 1];
		if (t < s) return c[sz(c) - 1];
		return c[lb(all(c), t) - c.begin()];
	}
	else {
		if (t > s) return c[0];
		if (t <= c[0]) return c[0];
		if (c[sz(c) - 1] <= t) return c[sz(c) - 1];
		return c[ub(all(c), t) - c.begin() - 1];
	}
}

Compilation message

stations.cpp: In function 'void dfs(int, int, int)':
stations.cpp:29:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
stations.cpp:44:2: note: in expansion of macro 'EACH'
   44 |  EACH(v, adj[u]) {
      |  ^~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
stations.cpp:54:2: note: in expansion of macro 'FOR'
   54 |  FOR(i, 0, N - 1) adj[i].clear();
      |  ^~~
stations.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
stations.cpp:55:2: note: in expansion of macro 'FOR'
   55 |  FOR(i, 0, N - 2) {
      |  ^~~
stations.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
stations.cpp:62:2: note: in expansion of macro 'FOR'
   62 |  FOR(i, 0, N - 1) b.pb(l[i]);
      |  ^~~
stations.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
stations.cpp:64:2: note: in expansion of macro 'FOR'
   64 |  FOR(i, 0, N - 1) l[i] = lb(all(b), l[i]) - b.begin();
      |  ^~~
stations.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
stations.cpp:66:2: note: in expansion of macro 'FOR'
   66 |  FOR(i, 0, N - 1) l1.pb(l[i]);
      |  ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 916 KB Output is correct
2 Correct 457 ms 672 KB Output is correct
3 Correct 784 ms 544 KB Output is correct
4 Correct 621 ms 540 KB Output is correct
5 Correct 554 ms 540 KB Output is correct
6 Correct 404 ms 676 KB Output is correct
7 Correct 439 ms 536 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 1 ms 620 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 616 KB Output is correct
2 Correct 565 ms 664 KB Output is correct
3 Correct 841 ms 536 KB Output is correct
4 Correct 661 ms 528 KB Output is correct
5 Correct 552 ms 544 KB Output is correct
6 Correct 436 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 664 KB Output is correct
2 Correct 447 ms 664 KB Output is correct
3 Correct 775 ms 528 KB Output is correct
4 Correct 684 ms 540 KB Output is correct
5 Correct 526 ms 544 KB Output is correct
6 Correct 416 ms 648 KB Output is correct
7 Correct 460 ms 524 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 5 ms 628 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 669 ms 540 KB Output is correct
12 Correct 445 ms 768 KB Output is correct
13 Correct 477 ms 780 KB Output is correct
14 Correct 439 ms 532 KB Output is correct
15 Correct 51 ms 624 KB Output is correct
16 Correct 70 ms 676 KB Output is correct
17 Correct 122 ms 668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 700 KB Output is correct
2 Correct 618 ms 600 KB Output is correct
3 Correct 556 ms 544 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 6 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 571 ms 544 KB Output is correct
8 Correct 946 ms 520 KB Output is correct
9 Correct 610 ms 544 KB Output is correct
10 Correct 558 ms 660 KB Output is correct
11 Correct 5 ms 756 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 508 ms 668 KB Output is correct
17 Correct 422 ms 548 KB Output is correct
18 Correct 509 ms 704 KB Output is correct
19 Correct 467 ms 544 KB Output is correct
20 Correct 472 ms 676 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 660 KB Output is correct
2 Correct 362 ms 548 KB Output is correct
3 Correct 860 ms 536 KB Output is correct
4 Correct 524 ms 544 KB Output is correct
5 Correct 650 ms 420 KB Output is correct
6 Correct 427 ms 668 KB Output is correct
7 Correct 452 ms 544 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 0 ms 620 KB Output is correct
11 Correct 468 ms 536 KB Output is correct
12 Correct 531 ms 548 KB Output is correct
13 Correct 846 ms 544 KB Output is correct
14 Correct 659 ms 548 KB Output is correct
15 Correct 615 ms 676 KB Output is correct
16 Correct 461 ms 520 KB Output is correct
17 Correct 550 ms 548 KB Output is correct
18 Correct 432 ms 648 KB Output is correct
19 Correct 429 ms 676 KB Output is correct
20 Correct 404 ms 536 KB Output is correct
21 Correct 47 ms 600 KB Output is correct
22 Correct 74 ms 540 KB Output is correct
23 Correct 86 ms 676 KB Output is correct
24 Correct 5 ms 748 KB Output is correct
25 Correct 6 ms 620 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 2 ms 628 KB Output is correct
28 Correct 1 ms 624 KB Output is correct
29 Correct 512 ms 528 KB Output is correct
30 Correct 461 ms 540 KB Output is correct
31 Correct 469 ms 540 KB Output is correct
32 Correct 519 ms 548 KB Output is correct
33 Correct 480 ms 564 KB Output is correct
34 Correct 316 ms 548 KB Output is correct
35 Correct 417 ms 772 KB Output is correct
36 Correct 479 ms 752 KB Output is correct
37 Correct 478 ms 668 KB Output is correct
38 Correct 406 ms 652 KB Output is correct
39 Correct 403 ms 796 KB Output is correct
40 Correct 462 ms 660 KB Output is correct
41 Correct 445 ms 776 KB Output is correct
42 Correct 67 ms 576 KB Output is correct
43 Correct 107 ms 660 KB Output is correct
44 Correct 134 ms 764 KB Output is correct
45 Correct 124 ms 620 KB Output is correct
46 Correct 327 ms 548 KB Output is correct
47 Correct 271 ms 668 KB Output is correct
48 Correct 45 ms 740 KB Output is correct
49 Correct 60 ms 880 KB Output is correct