oj.uz

답안 #633355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633355 2022-08-22T07:53:28 Z ghostwriter 경주 (Race) (IOI11_race) C++14
100 / 100
 1439 ms 91168 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.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
		Practising for VOI23 gold medal
*/
const int oo = 1e9;
const int MAXN = 2e5 + 1;
const int MAXK = 1e6 + 1;
int n, k, h[MAXN], h1[MAXN], s[MAXN], c[MAXN], rs = oo;
vi vt;
vpi adj[MAXN];
multiset<int> hset[MAXK];
void dfs(int u, int p) {
	s[u] = 1;
	EACH(j, adj[u]) {
		int v = j.st, w = j.nd;
		if (c[v] || v == p) continue;
		h[v] = h[u] + w;
		h[v] = min(h[v], k + 1);
		h1[v] = h1[u] + 1;
		dfs(v, u);
		s[u] += s[v];
	}
}
void dfs1(int u, int p) {
	vt.pb(u);
	EACH(j, adj[u]) {
		int v = j.st;
		if (c[v] || v == p) continue;
		dfs1(v, u);
	}
}
int findct(int u, int p, int total) {
	EACH(j, adj[u]) {
		int v = j.st;
		if (c[v] || v == p) continue;
		if (s[v] > total / 2) return findct(v, u, total);
	}
	return u;
}
void centroid(int u) {
	h[u] = h1[u] = 0;
	dfs(u, 0);
	int ct = findct(u, 0, s[u]);
	h[ct] = h1[ct] = 0;
	dfs(ct, 0);
	c[ct] = 1;
	EACH(j, adj[ct]) {
		int v = j.st;
		if (c[v]) continue;
		dfs1(v, ct);
		EACH(z, vt) {
			int hn = h[z];
			if (hn == k) rs = min(rs, h1[z]);
			if (hn > k) continue;
			hset[hn].insert(h1[z]);
		}
		vt.clear();
	}
	EACH(j, adj[ct]) {
		int v = j.st;
		if (c[v]) continue;
		dfs1(v, ct);
		EACH(z, vt) {
			int hn = h[z];
			if (hn > k) continue;
			hset[hn].erase(hset[hn].lb(h1[z]));
		}
		EACH(z, vt) {
			int hn = h[z];
			if (hn > k) continue;
			int tmp = k - hn;
			if (!hset[tmp].empty()) rs = min(rs, h1[z] + *hset[tmp].begin());
		}
		EACH(z, vt) {
			int hn = h[z];
			if (hn > k) continue;
			hset[hn].insert(h1[z]);
		}
		vt.clear();
	}
	EACH(j, adj[ct]) {
		int v = j.st;
		if (c[v]) continue;
		dfs1(v, ct);
		EACH(z, vt) {
			int hn = h[z];
			if (hn > k) continue;
			hset[hn].erase(hset[hn].lb(h1[z]));
		}
		vt.clear();
	}
	EACH(j, adj[ct]) {
		int v = j.st;
		if (c[v]) continue;
		centroid(v);
	}
}
int best_path(int n, int k, int h[][2], int l[]) {
	::k = k;
	FOR(i, 0, n - 2) {
		int u = h[i][0] + 1, v = h[i][1] + 1, w = l[i];
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	centroid(1);
	return rs < oo? rs : -1;
}
/*
3 1
1 0 3
2 1 1
1
*/

Compilation message

race.cpp: In function 'void dfs(int, int)':
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:47:2: note: in expansion of macro 'EACH'
   47 |  EACH(j, adj[u]) {
      |  ^~~~
race.cpp: In function 'void dfs1(int, int)':
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:59:2: note: in expansion of macro 'EACH'
   59 |  EACH(j, adj[u]) {
      |  ^~~~
race.cpp: In function 'int findct(int, int, int)':
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:66:2: note: in expansion of macro 'EACH'
   66 |  EACH(j, adj[u]) {
      |  ^~~~
race.cpp: In function 'void centroid(int)':
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:80:2: note: in expansion of macro 'EACH'
   80 |  EACH(j, adj[ct]) {
      |  ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:84:3: note: in expansion of macro 'EACH'
   84 |   EACH(z, vt) {
      |   ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:92:2: note: in expansion of macro 'EACH'
   92 |  EACH(j, adj[ct]) {
      |  ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:96:3: note: in expansion of macro 'EACH'
   96 |   EACH(z, vt) {
      |   ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:101:3: note: in expansion of macro 'EACH'
  101 |   EACH(z, vt) {
      |   ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:107:3: note: in expansion of macro 'EACH'
  107 |   EACH(z, vt) {
      |   ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:114:2: note: in expansion of macro 'EACH'
  114 |  EACH(j, adj[ct]) {
      |  ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:118:3: note: in expansion of macro 'EACH'
  118 |   EACH(z, vt) {
      |   ^~~~
race.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
race.cpp:125:2: note: in expansion of macro 'EACH'
  125 |  EACH(j, adj[ct]) {
      |  ^~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
race.cpp:133:2: note: in expansion of macro 'FOR'
  133 |  FOR(i, 0, n - 2) {
      |  ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 51888 KB Output is correct
2 Correct 26 ms 52012 KB Output is correct
3 Correct 29 ms 51968 KB Output is correct
4 Correct 28 ms 51952 KB Output is correct
5 Correct 28 ms 51924 KB Output is correct
6 Correct 30 ms 51924 KB Output is correct
7 Correct 26 ms 51924 KB Output is correct
8 Correct 27 ms 51940 KB Output is correct
9 Correct 30 ms 51976 KB Output is correct
10 Correct 30 ms 51916 KB Output is correct
11 Correct 30 ms 51892 KB Output is correct
12 Correct 27 ms 51924 KB Output is correct
13 Correct 29 ms 51980 KB Output is correct
14 Correct 26 ms 51952 KB Output is correct
15 Correct 29 ms 51996 KB Output is correct
16 Correct 26 ms 51972 KB Output is correct
17 Correct 25 ms 51924 KB Output is correct
18 Correct 25 ms 52024 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 51888 KB Output is correct
2 Correct 26 ms 52012 KB Output is correct
3 Correct 29 ms 51968 KB Output is correct
4 Correct 28 ms 51952 KB Output is correct
5 Correct 28 ms 51924 KB Output is correct
6 Correct 30 ms 51924 KB Output is correct
7 Correct 26 ms 51924 KB Output is correct
8 Correct 27 ms 51940 KB Output is correct
9 Correct 30 ms 51976 KB Output is correct
10 Correct 30 ms 51916 KB Output is correct
11 Correct 30 ms 51892 KB Output is correct
12 Correct 27 ms 51924 KB Output is correct
13 Correct 29 ms 51980 KB Output is correct
14 Correct 26 ms 51952 KB Output is correct
15 Correct 29 ms 51996 KB Output is correct
16 Correct 26 ms 51972 KB Output is correct
17 Correct 25 ms 51924 KB Output is correct
18 Correct 25 ms 52024 KB Output is correct
19 Correct 25 ms 51992 KB Output is correct
20 Correct 29 ms 51968 KB Output is correct
21 Correct 27 ms 52000 KB Output is correct
22 Correct 26 ms 51992 KB Output is correct
23 Correct 26 ms 52044 KB Output is correct
24 Correct 26 ms 51972 KB Output is correct
25 Correct 34 ms 52072 KB Output is correct
26 Correct 33 ms 51984 KB Output is correct
27 Correct 31 ms 52068 KB Output is correct
28 Correct 27 ms 52068 KB Output is correct
29 Correct 27 ms 52032 KB Output is correct
30 Correct 28 ms 52108 KB Output is correct
31 Correct 26 ms 52124 KB Output is correct
32 Correct 26 ms 52100 KB Output is correct
33 Correct 27 ms 52000 KB Output is correct
34 Correct 28 ms 52092 KB Output is correct
35 Correct 36 ms 52028 KB Output is correct
36 Correct 26 ms 52056 KB Output is correct
37 Correct 26 ms 52048 KB Output is correct
38 Correct 27 ms 52120 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 51888 KB Output is correct
2 Correct 26 ms 52012 KB Output is correct
3 Correct 29 ms 51968 KB Output is correct
4 Correct 28 ms 51952 KB Output is correct
5 Correct 28 ms 51924 KB Output is correct
6 Correct 30 ms 51924 KB Output is correct
7 Correct 26 ms 51924 KB Output is correct
8 Correct 27 ms 51940 KB Output is correct
9 Correct 30 ms 51976 KB Output is correct
10 Correct 30 ms 51916 KB Output is correct
11 Correct 30 ms 51892 KB Output is correct
12 Correct 27 ms 51924 KB Output is correct
13 Correct 29 ms 51980 KB Output is correct
14 Correct 26 ms 51952 KB Output is correct
15 Correct 29 ms 51996 KB Output is correct
16 Correct 26 ms 51972 KB Output is correct
17 Correct 25 ms 51924 KB Output is correct
18 Correct 25 ms 52024 KB Output is correct
19 Correct 421 ms 60488 KB Output is correct
20 Correct 437 ms 60244 KB Output is correct
21 Correct 498 ms 61532 KB Output is correct
22 Correct 476 ms 63932 KB Output is correct
23 Correct 215 ms 60328 KB Output is correct
24 Correct 141 ms 60168 KB Output is correct
25 Correct 479 ms 63628 KB Output is correct
26 Correct 453 ms 71900 KB Output is correct
27 Correct 349 ms 68356 KB Output is correct
28 Correct 799 ms 82780 KB Output is correct
29 Correct 752 ms 81652 KB Output is correct
30 Correct 381 ms 68136 KB Output is correct
31 Correct 323 ms 68220 KB Output is correct
32 Correct 488 ms 68216 KB Output is correct
33 Correct 670 ms 67312 KB Output is correct
34 Correct 543 ms 68040 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 51888 KB Output is correct
2 Correct 26 ms 52012 KB Output is correct
3 Correct 29 ms 51968 KB Output is correct
4 Correct 28 ms 51952 KB Output is correct
5 Correct 28 ms 51924 KB Output is correct
6 Correct 30 ms 51924 KB Output is correct
7 Correct 26 ms 51924 KB Output is correct
8 Correct 27 ms 51940 KB Output is correct
9 Correct 30 ms 51976 KB Output is correct
10 Correct 30 ms 51916 KB Output is correct
11 Correct 30 ms 51892 KB Output is correct
12 Correct 27 ms 51924 KB Output is correct
13 Correct 29 ms 51980 KB Output is correct
14 Correct 26 ms 51952 KB Output is correct
15 Correct 29 ms 51996 KB Output is correct
16 Correct 26 ms 51972 KB Output is correct
17 Correct 25 ms 51924 KB Output is correct
18 Correct 25 ms 52024 KB Output is correct
19 Correct 25 ms 51992 KB Output is correct
20 Correct 29 ms 51968 KB Output is correct
21 Correct 27 ms 52000 KB Output is correct
22 Correct 26 ms 51992 KB Output is correct
23 Correct 26 ms 52044 KB Output is correct
24 Correct 26 ms 51972 KB Output is correct
25 Correct 34 ms 52072 KB Output is correct
26 Correct 33 ms 51984 KB Output is correct
27 Correct 31 ms 52068 KB Output is correct
28 Correct 27 ms 52068 KB Output is correct
29 Correct 27 ms 52032 KB Output is correct
30 Correct 28 ms 52108 KB Output is correct
31 Correct 26 ms 52124 KB Output is correct
32 Correct 26 ms 52100 KB Output is correct
33 Correct 27 ms 52000 KB Output is correct
34 Correct 28 ms 52092 KB Output is correct
35 Correct 36 ms 52028 KB Output is correct
36 Correct 26 ms 52056 KB Output is correct
37 Correct 26 ms 52048 KB Output is correct
38 Correct 27 ms 52120 KB Output is correct
39 Correct 421 ms 60488 KB Output is correct
40 Correct 437 ms 60244 KB Output is correct
41 Correct 498 ms 61532 KB Output is correct
42 Correct 476 ms 63932 KB Output is correct
43 Correct 215 ms 60328 KB Output is correct
44 Correct 141 ms 60168 KB Output is correct
45 Correct 479 ms 63628 KB Output is correct
46 Correct 453 ms 71900 KB Output is correct
47 Correct 349 ms 68356 KB Output is correct
48 Correct 799 ms 82780 KB Output is correct
49 Correct 752 ms 81652 KB Output is correct
50 Correct 381 ms 68136 KB Output is correct
51 Correct 323 ms 68220 KB Output is correct
52 Correct 488 ms 68216 KB Output is correct
53 Correct 670 ms 67312 KB Output is correct
54 Correct 543 ms 68040 KB Output is correct
55 Correct 48 ms 53004 KB Output is correct
56 Correct 66 ms 53124 KB Output is correct
57 Correct 520 ms 64732 KB Output is correct
58 Correct 115 ms 64336 KB Output is correct
59 Correct 352 ms 71864 KB Output is correct
60 Correct 1439 ms 91168 KB Output is correct
61 Correct 356 ms 70048 KB Output is correct
62 Correct 536 ms 77184 KB Output is correct
63 Correct 692 ms 77396 KB Output is correct
64 Correct 1401 ms 78000 KB Output is correct
65 Correct 519 ms 69212 KB Output is correct
66 Correct 1339 ms 79552 KB Output is correct
67 Correct 330 ms 77904 KB Output is correct
68 Correct 628 ms 73260 KB Output is correct
69 Correct 662 ms 73376 KB Output is correct
70 Correct 619 ms 72444 KB Output is correct