제출 #379676

#제출 시각아이디문제언어결과실행 시간메모리
379676mode149256공장들 (JOI14_factories)C++17
33 / 100
8080 ms251600 KiB
/*input */ #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #include "factories.h" using namespace std; namespace my_template { typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd; typedef vector<int> vi; typedef vector<vi> vii; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<vl> vll; typedef vector<pi> vpi; typedef vector<vpi> vpii; typedef vector<pl> vpl; typedef vector<cd> vcd; typedef vector<pd> vpd; typedef vector<bool> vb; typedef vector<vb> vbb; typedef std::string str; typedef std::vector<str> vs; #define x first #define y second #define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n" const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L; template<typename T> pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); } template<typename T> pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); } template<typename T> T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); } template<typename T> T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); } template<typename T> void print(vector<T> vec, string name = "") { cout << name; for (auto u : vec) cout << u << ' '; cout << '\n'; } } using namespace my_template; const int MOD = 1000000007; const ll INF = 1e14; const int MX = 500101; const int L = 19; int n; vector<vector<pair<int, ll>>> edges; vi dep; vl toRoot; vii p; vll w; vi in; vi out; int piv; void dfs(int x, int par) { in[x] = piv++; for (auto u : edges[x]) { if (u.x == par) continue; int b = u.x; dep[b] = dep[x] + 1; toRoot[b] = toRoot[x] + u.y; p[b][0] = x; w[b][0] = u.y; for (int i = 1; i < L; ++i) { p[b][i] = p[p[b][i - 1]][i - 1]; w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1]; } dfs(u.x, x); } out[x] = piv; } // a is ancestor of b int anc(int a, int b) { return in[a] < in[b] and out[b] <= out[a]; } int lca(int a, int b) { if (dep[a] > dep[b]) swap(a, b); // a // b for (int i = L - 1; i >= 0; --i) { if (dep[b] - (1 << i) >= dep[a]) b = p[b][i]; } assert(dep[a] == dep[b]); if (a == b) return a; for (int i = L - 1; i >= 0; i--) { if (p[a][i] != p[b][i]) { a = p[a][i]; b = p[b][i]; } } return p[a][0]; } ll dis(int a, int b) { int l = lca(a, b); return toRoot[a] + toRoot[b] - 2 * toRoot[l]; } void make_lca() { dep = vi(n); p = vii(n, vi(L, 0)); w = vll(n, vl(L, 0)); toRoot = vl(n); in = vi(n); out = vi(n); dep[0] = 0; p[0][0] = 0; w[0][0] = 0; toRoot[0] = 0; piv = 0; dfs(0, -1); } vi kas; void Init(int N, int A[], int B[], int D[]) { n = N; edges.resize(N); kas = vi(N, -1); for (int i = 0; i < N - 1; ++i) { int a = A[i]; int b = B[i]; int d = D[i]; edges[a].emplace_back(b, d); edges[b].emplace_back(a, d); } make_lca(); } ll Query(int S, int X[], int T, int Y[]) { vi visi; for (int i = 0; i < S; ++i) { visi.emplace_back(X[i]); kas[X[i]] = 1; } for (int i = 0; i < T; ++i) { visi.emplace_back(Y[i]); kas[Y[i]] = 2; } sort(visi.begin(), visi.end(), [&](const int & a, const int & b) { return in[a] < in[b]; }); for (int i = 1; i < S + T; ++i) { int l = lca(visi[i - 1], visi[i]); visi.emplace_back(l); if (kas[l] == -1) kas[l] = 0; } sort(visi.begin(), visi.end(), [&](const int & a, const int & b) { return in[a] < in[b]; }); visi.erase(unique(visi.begin(), visi.end()), visi.end()); // print(visi); ll ats = INF; unordered_map<int, vl> low; vector<int> ver; ver.emplace_back(visi[0]); low[visi[0]] = vl{INF, INF}; if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0; for (int i = 1; i < (int)visi.size(); ++i) { while (!anc(ver.back(), visi[i])) { int a = ver.back(); ver.pop_back(); int b = ver.back(); ll d = dis(a, b); if (kas[a] + kas[b] == 3) ats = min(ats, d); // b // / c // a low[b][0] = min(low[b][0], low[a][0] + d); low[b][1] = min(low[b][1], low[a][1] + d); } ver.emplace_back(visi[i]); low[visi[i]] = vl{INF, INF}; if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0; } while (ver.size() >= 2) { int a = ver.back(); ver.pop_back(); int b = ver.back(); ll d = dis(a, b); // printf("a = %d, b = %d, d = %lld\n", a, b, d); if (kas[a] + kas[b] == 3) ats = min(ats, d); // b // / c // a low[b][0] = min(low[b][0], low[a][0] + d); low[b][1] = min(low[b][1], low[a][1] + d); } for (auto u : visi) { // printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]); ats = min(ats, low[u][0] + low[u][1]); kas[u] = -1; } return ats; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...