| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230912 | bb2009 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define roadtovoai ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define first fi
#define second se
#define pb push_back
#define eb emplace_back
const int MAXN = 5e5+5;
const int INF = 1e18;
int n,q;
int depth[MAXN], tin[MAXN], tout[MAXN], timer, par[MAXN][20], dist[MAXN], dp[MAXN]; // par[i][j] = to tien cua dinh i sau 2^j buoc di tren cay
bool visited[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<pair<int,int>> vt[MAXN];
void dfs(int u, int e){
par[u][0] = e;
tin[u] = ++timer;
for(int i=1; i<=17; i++){
par[u][i] = par[par[u][i-1]][i-1];
}
for(auto [to, w] : adj[u]){
if(to == e) continue;
depth[to] = depth[u] + 1;
dist[to] = dist[u] + w;
dfs(to, u);
}
tout[u] = timer;
}
bool vtsort(int u, int v){
return tin[u] < tin[v];
}
bool check(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v){
if(check(u,v)) return u;
if(check(v,u)) return v;
for(int i=17; i>=0; i--){
if(depth[u] >= (1<<i) && !check(par[u][i], v)){
u = par[u][i];
}
}
return par[u][0];
}
int get(int u,int v){
int tt = LCA(u,v);
return dist[u] + dist[v] - 2*dist[tt];
}
void init(int n, int a[], int b[], int c[]){
for(int i=0; i<n-1; i++){
adj[a[i]].pb({b[i], c[i]});
adj[b[i]].pb({a[i], c[i]});
}
for(int i=0; i<=17; i++){
par[0][i] = 0;
}
depth[0] = 0;
dist[0] = 0;
dfs(0, 0);
memset(dp, -1, sizeof(dp));
}
int solve2(int s, int x[], int t, int y[]){
vector<int> sp;
for(int i=0; i<s; i++){
sp.pb(x[i]);
}
for(int i=0; i<t; i++){
sp.pb(y[i]);
dp[y[i]] = 0;
}
sort(sp.begin(), sp.end(), vtsort);
vector<int> node = sp;
for(int i=1; i<sp.size();i++){
node.pb(LCA(sp[i-1], sp[i]));
}
sort(node.begin(), node.end(), vtsort);
node.erase(unique(node.begin(),node.end()), node.end());
stack<int> st;
st.push(node[0]);
for(int i=1; i<node.size(); i++){
int u = node[i];
while(!check(st.top(),u)){
st.pop();
}
int v = st.top();
int d = get(u, v);
vt[u].pb({v, d});
vt[v].pb({u,d});
st.push(u);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for(int i=0; i<s; i++){
pq.push({0, x[i]});
}
int ans = INF;
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(dp[u] == 0){
ans = d;
break;
}
if(visited[u]) continue;
for(auto [to, w] : vt[u]){
pq.push({d+w, to});
}
}
for(int u : node){
vt[u].clear();
visited[u] = 0;
dp[u] = -1;
}
return ans;
}