제출 #639971

#제출 시각아이디문제언어결과실행 시간메모리
639971ghostwriter공장들 (JOI14_factories)C++14
100 / 100
5079 ms195624 KiB
#include "factories.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 Cay ngay cay dem nhung deo duoc cong nhan */ const ll oo = 1e18; const int MAXN = 5e5 + 5; const int Nx2 = 1e6 + 5; int n, h[MAXN], a[Nx2][20], tin[MAXN], LOG[Nx2], s[MAXN], c[MAXN], p[MAXN], cnt = 0; ll d[MAXN], f[MAXN]; vpi adj[MAXN]; void dfs(int u, int p) { a[++cnt][0] = u; EACH(j, adj[u]) { int v = j.st, w = j.nd; if (v == p) continue; d[v] = d[u] + w; h[v] = h[u] + 1; dfs(v, u); a[++cnt][0] = u; } } int lca(int a, int b) { a = tin[a]; b = tin[b]; if (a > b) swap(a, b); int len = LOG[b - a + 1]; int f = ::a[a][len], s = ::a[b - (1 << len) + 1][len]; if (h[f] < h[s]) return f; return s; } ll dis(int a, int b) { return d[a] + d[b] - 2 * d[lca(a, b)]; } void dfs1(int u, int p) { s[u] = 1; EACH(j, adj[u]) { int v = j.st; if (v == p || c[v]) continue; dfs1(v, u); s[u] += s[v]; } } int fct(int u, int p, int s) { EACH(j, adj[u]) { int v = j.st; if (v == p || c[v]) continue; if (2 * ::s[v] > s) return fct(v, u, s); } return u; } void centroid(int u, int p) { dfs1(u, 0); int ct = fct(u, 0, s[u]); ::p[ct] = p; c[ct] = 1; EACH(j, adj[ct]) { int v = j.st; if (v == p || c[v]) continue; centroid(v, ct); } } void Init(int N, int A[], int B[], int D[]) { n = N; FOR(i, 0, N - 2) { int u = A[i] + 1, v = B[i] + 1, w = D[i]; adj[u].pb({v, w}); adj[v].pb({u, w}); } dfs(1, 0); FOS(i, cnt, 1) tin[a[i][0]] = i; FOR(j, 1, 19) FOR(i, 1, cnt) { if (i + (1 << j) - 1 > cnt) break; int f = a[i][j - 1], s = a[i + (1 << (j - 1))][j - 1]; if (h[f] < h[s]) a[i][j] = f; else a[i][j] = s; } FOR(i, 1, Nx2 - 1) LOG[i] = log2(i); centroid(1, 0); FOR(i, 1, n) f[i] = oo; } long long Query(int S, int X[], int T, int Y[]) { FOR(i, 0, S - 1) { int u = X[i] + 1, cur = u; WHILE(cur) { f[cur] = min(f[cur], dis(u, cur)); cur = p[cur]; } } ll rs = oo; FOR(i, 0, T - 1) { int u = Y[i] + 1, cur = u; WHILE(cur) { rs = min(rs, f[cur] + dis(u, cur)); cur = p[cur]; } } FOR(i, 0, S - 1) { int u = X[i] + 1, cur = u; WHILE(cur) { f[cur] = oo; cur = p[cur]; } } return rs; }

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

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:46:5: note: in expansion of macro 'EACH'
   46 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:67:5: note: in expansion of macro 'EACH'
   67 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'int fct(int, int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:75:5: note: in expansion of macro 'EACH'
   75 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'void centroid(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:87:5: note: in expansion of macro 'EACH'
   87 |     EACH(j, adj[ct]) {
      |     ^~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i, 0, N - 2) {
      |     ^~~
factories.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
factories.cpp:101:5: note: in expansion of macro 'FOS'
  101 |     FOS(i, cnt, 1) tin[a[i][0]] = i;
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:102:5: note: in expansion of macro 'FOR'
  102 |     FOR(j, 1, 19)
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:103:5: note: in expansion of macro 'FOR'
  103 |     FOR(i, 1, cnt) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:109:5: note: in expansion of macro 'FOR'
  109 |     FOR(i, 1, Nx2 - 1) LOG[i] = log2(i);
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i, 1, n) f[i] = oo;
      |     ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:114:5: note: in expansion of macro 'FOR'
  114 |     FOR(i, 0, S - 1) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:122:5: note: in expansion of macro 'FOR'
  122 |     FOR(i, 0, T - 1) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:129:5: note: in expansion of macro 'FOR'
  129 |     FOR(i, 0, S - 1) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...