| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 683301 | whqkrtk04 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
vector<vector<int>> S, E;
vector<int> P, L;
vector<ll> D, DU, DV;
vector<bool> U, V;
int lca(int x, int y) {
if(L[x] < L[y]) swap(x, y);
for(int i = 19; i >= 0; i--)
if(L[S[x][i]] >= L[y])
x = S[x][i];
if(x == y) return x;
for(int i = 19; i >= 0; i--)
if(S[x][i] != S[y][i])
x = S[x][i], y = S[y][i];
return P[x];
}
void make_sparse() {
//cout << "Make Sparse\n";
S.resize(P.size(), vector<int>(20));
for(int i = 0; i < P.size(); i++) S[i][0] = P[i];
for(int i = 0; i < P.size(); i++)
for(int j = 1; j < 20; j++)
S[i][j] = S[S[i][j-1]][j-1];
}
void dfs(int x, int p, ll d, int l, vector<bool> &vis, vector<vector<pii>> &E) {
if(vis[x]) return;
vis[x] = true;
P[x] = p; D[x] = d; L[x] = l;
for(auto &i : E[x]) dfs(i.fi, x, d+i.se, l+1, vis, E);
}
ll solve(int x) {
ll ans = LLINF;
if(U[x]) DU[x] = min(DU[x], D[x]);
if(V[x]) DV[x] = min(DV[x], D[x]);
for(auto i : E[x]) {
ans = min(ans, solve(i));
DV[x] = min(DV[x], DV[i]);
DU[x] = min(DU[x], DU[i]);
}
ans = min(ans, DV[x]+DU[x]-2*D[x]);
return ans;
}
void sort_vertex(vector<int> &vertex) {
sort(vertex.begin(), vertex.end(), [&](int &a, int &b){ return I[a] < I[b]; });
vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}
void make_tree(vector<int> &M) {
int tmpsize = M.size();
for(int i = 1; i < tmpsize; i++) M.push_back(lca(M[i-1], M[i]));
sort_vertex(M);
for(int i = 1; i < M.size(); i++) E[lca(M[i-1], M[i])].push_back(M[i]);
}
void Init(int N, int A[], int B[], int X[]) {
//cout << "Init\n";
vector<bool> vis(N, false);
E.resize(N); U.resize(N, false); V.resize(N, false);
DU.resize(N, LLINF); DV.resize(N, LLINF);
vector<vector<pii>> T(N);
for(int i = 0; i < N-1; i++) {
T[A[i]].push_back({B[i], X[i]});
T[B[i]].push_back({A[i], X[i]});
}
P.resize(N); D.resize(N); L.resize(N);
dfs(0, 0, 0LL, 0, vis, T);
//cout << P;
make_sparse();
}
ll Query(int S, int X[], int T, int Y[]) {
//cout << "query " << S << " " << T << "\n";
vector<int> XX(X, X+S), YY(Y, Y+T), M;
for(auto i : XX) { M.push_back(i); U[i] = true; }
for(auto i : YY) { M.push_back(i); V[i] = true; }
sort_vertex(M);
make_tree(M);
ll ans = solve(M[0]);
//assert(DU[M[0]] < LLINF && DV[M[0]] < LLINF);
for(auto i : M) {
U[i] = V[i] = false;
DU[i] = DV[i] = LLINF;
E[i].clear();
}
return ans;
}