제출 #387836

#제출 시각아이디문제언어결과실행 시간메모리
387836maksim1744공장들 (JOI14_factories)C++17
0 / 100
35 ms836 KiB
/* author: Maksim1744 created: 09.04.2021 12:06:25 */ #include "bits/stdc++.h" using namespace std; #define ll long long #define ld long double #define mp make_pair #define pb push_back #define eb emplace_back #define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin()) #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin()) #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin()) template<typename T> vector<T>& operator-- (vector<T>& v){for (auto& i : v) --i; return v;} template<typename T> vector<T>& operator++ (vector<T>& v){for (auto& i : v) ++i; return v;} template<typename T> istream& operator>>(istream& is, vector<T>& v){for (auto& i : v) is >> i; return is;} template<typename T> ostream& operator<<(ostream& os, vector<T>& v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;} template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;} template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second; return is;} template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;} template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);} template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);} template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;} template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;} #ifdef HOME #define SHOW_COLORS #include "C:/C++ libs/print.cpp" #else #define show(...) 42 #define mclock 42 #define shows 42 #define debug if (false) #endif vector<int> lca_ind; vector<vector<int>> lca_sparse; vector<int> lca_p2; vector<int> lca_depth; vector<ll> lca_w_depth; vector<int> tin, tout; void build_lca_sparse(vector<vector<pair<int, int>>>& g, int root = 0) { int n = g.size(); vector<int> euler; lca_ind.resize(n); lca_depth.assign(n, -1); lca_w_depth.assign(n, 0); tin.resize(n); tout.resize(n); int timer = 0; function<void(int, int)> dfs = [&](int v, int depth) { lca_ind[v] = euler.size(); euler.pb(v); tin[v] = timer++; lca_depth[v] = depth; for (auto [k, w] : g[v]) { if (lca_depth[k] == -1) { lca_w_depth[k] = lca_w_depth[v] + w; dfs(k, depth + 1); euler.pb(v); } } tout[v] = timer++; }; dfs(root, 0); int m = euler.size(); int log = 1; while ((1 << log) < m) ++log; lca_sparse.resize(log); lca_sparse[0].resize(m); lca_p2.resize(m + 1); int pp2 = 0; for (int i = 1; i < lca_p2.size(); ++i) { if (1 << (pp2 + 1) <= i) ++pp2; lca_p2[i] = pp2; } lca_p2[0] = 0; for (int i = 0; i < m; ++i) lca_sparse[0][i] = euler[i]; for (int i = 1; i < log; ++i) { lca_sparse[i].assign(m, 0); for (int j = 0; j < m - (1 << (i - 1)); ++j) { int v1 = lca_sparse[i - 1][j], v2 = lca_sparse[i - 1][j + (1 << (i - 1))]; if (lca_depth[v1] < lca_depth[v2]) lca_sparse[i][j] = v1; else lca_sparse[i][j] = v2; } } } int get_lca(int u, int v) { if (u == v) return u; u = lca_ind[u]; v = lca_ind[v]; if (u > v) swap(u, v); int v1 = lca_sparse[lca_p2[v - u + 1]][u], v2 = lca_sparse[lca_p2[v - u + 1]][v - (1 << lca_p2[v - u + 1]) + 1]; if (lca_depth[v1] < lca_depth[v2]) return v1; else return v2; } ll dist(int u, int v) { return lca_w_depth[u] + lca_w_depth[v] - 2 * lca_w_depth[get_lca(u, v)]; } vector<vector<pair<int, ll>>> g0; vector<ll> dd; vector<int> tp; void Init(int N, int A[], int B[], int D[]) { int n = N; tp.resize(n); g0.resize(n); dd.resize(n); vector<vector<pair<int, int>>> g(n); for (int i = 0; i < n; ++i) { g[A[i]].eb(B[i], D[i]); g[B[i]].eb(A[i], D[i]); } build_lca_sparse(g, 0); } long long Query(int S, int X[], int T, int Y[]) { vector<int> vert; for (int i = 0; i < S; ++i) { vert.pb(X[i]); tp[X[i]] = 1; } for (int i = 0; i < T; ++i) { vert.pb(Y[i]); tp[Y[i]] = 2; } sort(vert.begin(), vert.end()); vert.erase(unique(vert.begin(), vert.end()), vert.end()); if (vert.size() != S + T) return 0; sort(vert.begin(), vert.end(), [&](int i, int j) {return tin[i] < tin[j];}); int sz = vert.size(); for (int i = 0; i < sz; ++i) { vert.pb(get_lca(vert[i], vert[(i + 1) % sz])); } vector<pair<int, int>> ev; for (int v : vert) { ev.eb(tin[v], v); ev.eb(tout[v], v); } sort(ev.begin(), ev.end()); show(ev); vector<int> path; ll ans = 1e18; for (auto [tm, v] : ev) { if (!path.empty() && path.back() == v) { path.pop_back(); } else { if (!path.empty()) { int u = path.back(); ll d = dist(u, v); g0[u].eb(v, d); g0[v].eb(u, d); } path.pb(v); } } priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; for (int k : vert) dd[k] = 1e18; for (int i = 0; i < S; ++i) { q.emplace(0, X[i]); dd[X[i]] = 0; } show(vert); show(q); show(g0); show(dd); while (!q.empty()) { auto [D, v] = q.top(); q.pop(); if (dd[v] < D) continue; for (auto [k, w] : g0[v]) { if (dd[k] > dd[v] + w) { dd[k] = dd[v] + w; q.emplace(dd[k], k); } } } show(dd); for (int i = 0; i < T; ++i) ans = min(ans, dd[Y[i]]); for (int k : vert) g0[k].clear(); return ans; }

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

factories.cpp: In function 'void build_lca_sparse(std::vector<std::vector<std::pair<int, int> > >&, int)':
factories.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 1; i < lca_p2.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:154:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  154 |     if (vert.size() != S + T) return 0;
      |         ~~~~~~~~~~~~^~~~~~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:166:5: note: in expansion of macro 'show'
  166 |     show(ev);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:191:5: note: in expansion of macro 'show'
  191 |     show(vert);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:192:5: note: in expansion of macro 'show'
  192 |     show(q);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:193:5: note: in expansion of macro 'show'
  193 |     show(g0);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:194:5: note: in expansion of macro 'show'
  194 |     show(dd);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:207:5: note: in expansion of macro 'show'
  207 |     show(dd);
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...