제출 #633351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633351		ghostwriter	Race (IOI11_race)	C++14	0 / 100	28 ms	52064 KiB

race

#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;
		// debug(u, v, w, h[v]);
		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, -1);
	// debug(u, h[2]);
	int ct = findct(u, 0, s[u]);
	h[ct] = h1[ct] = 0;
	dfs(ct, -1);
	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];
			// debug(ct, z, hn, hset[hn]);
			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], v = h[i][1], w = l[i];
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	centroid(0);
	return rs < oo? rs : -1;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

컴파일 시 표준 에러 (stderr) 메시지

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:60:2: note: in expansion of macro 'EACH'
   60 |  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:67:2: note: in expansion of macro 'EACH'
   67 |  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:82:2: note: in expansion of macro 'EACH'
   82 |  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:86:3: note: in expansion of macro 'EACH'
   86 |   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:94:2: note: in expansion of macro 'EACH'
   94 |  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:98:3: note: in expansion of macro 'EACH'
   98 |   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:103:3: note: in expansion of macro 'EACH'
  103 |   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:109:3: note: in expansion of macro 'EACH'
  109 |   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:116:2: note: in expansion of macro 'EACH'
  116 |  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:120:3: note: in expansion of macro 'EACH'
  120 |   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:127:2: note: in expansion of macro 'EACH'
  127 |  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:135:2: note: in expansion of macro 'FOR'
  135 |  FOR(i, 0, n - 2) {
      |  ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57