| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1266457 | trinm01 | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>
const ll mod = 1e9 + 7;
const int MAXN = 5e5 + 5;
const ll oo = 1e18+7;
const int base = 0;
int n, qq;
vector<pii> adj[MAXN];
int d[MAXN], up[MAXN][20], h[MAXN], in[MAXN], out[MAXN], cnt;
void dfs(int u, int p){
in[u]=out[u]=++cnt;
for(auto [v, w]:adj[u]){
if(v==p) continue;
d[v]=d[u]+w;
h[v]=h[u]+1;
up[v][0]=u;
FOR(i, 1, 19){
up[v][i]=up[up[v][i-1]][i-1];
}
dfs(v, u);
out[u]=max(out[u], out[v]);
}
}
int lca(int u, int v){
if(h[u]!=h[v]){
if(h[u]<h[v]) swap(u, v);
int k=h[u]-h[v];
FOR(i, 0, 19){
if((k>>i)&1){
u=up[u][i];
}
}
}
if(u==v) return u;
FOD(i, 19, 0){
if(up[u][i]!=up[v][i]){
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
int dist(int u, int v){
return d[u]+d[v]-2*d[lca(u, v)];
}
bool cmp(int u, int v){
return in[u]<in[v];
}
bool inside(int u, int v){
if(in[u]<=in[v] && out[u]>=out[v]){
return 1;
}
return 0;
}
vector<pii> adj1[MAXN];
int f[MAXN];
void dijsktra(vector<int> &a, vector<int> &b){
priority_queue<pii, vector<pii>, greater<pii>> q;
for(auto x:b){
f[x]=oo;
}
for(auto x:a){
f[x]=0;
q.push({0, x});
}
while(!q.empty()){
auto [c, u]=q.top();
q.pop();
if(c>f[u]) continue;
for(auto [v, w]:adj1[u]){
if(f[v]>f[u]+w){
f[v]=f[u]+w;
q.push({f[v], v});
}
}
}
}
int solve(int p, int q, vector<int> &a, vector<int> &b){
vector<int> vec;
for(auto x:a){
vec.push_back(x);
}
for(auto x:b){
vec.push_back(x);
}
sort(vec.begin(), vec.end(), cmp);
FOR(i, 1, p+q-1){
vec.push_back(lca(vec[i], vec[i-1]));
}
sort(vec.begin(), vec.end(), cmp);
vec.erase(unique(vec.begin(), vec.end()), vec.end());
stack<int> st;
st.push(vec[0]);
// cout << vec[0] << ' ';
FOR(i, 1, vec.size()-1){
while(!inside(st.top(), vec[i])){
st.pop();
}
adj1[st.top()].push_back({vec[i], dist(st.top(), vec[i])});
adj1[vec[i]].push_back({st.top(), dist(st.top(), vec[i])});
// cout << st.top() << ' ' << vec[i] << ' ' << dist(st.top(), vec[i]) << '\n';
st.push(vec[i]);
// cout << vec[i] << ' ';
}
dijsktra(a, vec);
int ans=oo;
for(auto x:b){
ans=min(ans, f[x]);
}
for(auto x:vec){
adj[x].clear();
}
return ans;
}
void Init(int N, int A[], int B[], int D[]){
n=N;
FOR(i, 0, n-1){
adj[i].clear();
}
FOR(i, 0, n-2){
int u, v, c;
u=A[i], v=B[i], c=D[i];
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
cnt=0;
dfs(0, -1);
}
long long Query(int S, int X[], int T, int Y[]){
int p=S, q=T;
vector<int> a, b;
FOR(i, 0, S-1){
a.push_back(X[i]);
}
FOR(i, 0, T-1){
b.push_back(Y[i]);
}
return solve(p, q, a, b);
}