| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301291 | hg-2008 | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "lost.h"
//In the name of God
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
/*
_ _ _ _
| \ | | | | (_)
| \| | ___ ___| | ___
| . ` |/ _ \/ _ \ |/ / |
| |\ | __/ __/ <| |
|_| \_|\___|\___|_|\_\_|
*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=5e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
// #define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
lli tmp;
int n;
vector<pair<int,int>> adj[N];
bool mark[N];
bool vis[N];
int sz[N];
vector<int> ver;
int mxs[N];
int Par[N];
lli dis[N];
ve dist[N];
lli f[N];
void dfs1(lli v){
ver.PB(v);
vis[v] = 1;
sz[v] = 1;
for(auto [u,w] : adj[v]){
if(vis[u] == 1 || mark[u] == 1)continue;
dfs1(u);
sz[v] += sz[u];
mxs[v] = max(mxs[v],sz[u]);
}
}
void dfs2(lli v){
vis[v] = 1;
dist[v].PB(dis[v]);
// if(v == 0){
// debug(dist[0].back());
// }
for(auto [u,w] : adj[v]){
if(vis[u] == 1 || mark[u] == 1)continue;
dis[u] = dis[v] + w;
dfs2(u);
}
}
void cent_decomp(lli yek,lli pedar = -1){
dfs1(yek);
int m = SZ(ver);
int cent = -1;
for(int v : ver){
if(mxs[v] * 2 <= m && (m-sz[v])*2 <= m){
cent = v;
}
vis[v] = 0;
}
Par[cent] = pedar;
dfs2(cent);
for(auto u : ver){
dis[u] = 0;
vis[u] = 0;
sz[u] = 0,mxs[u] = 0;
}
mark[cent] = 1;
vis[cent] = 1;
ver.clear();
for(auto [v,w] : adj[cent]){
if(mark[v] == 0){
cent_decomp(v,cent);
}
}
}
void Init(int nud, int A[], int B[], int D[]) {
n = nud;
FOR(i,n-1){
lli a = A[i],b = B[i],c = D[i];
adj[a].PB(MP(b,c));
adj[b].PB(MP(a,c));
}
FOR(i,n)f[i] = INF;
cent_decomp(0,-1);
}
ve change;
void add(lli v){
lli C = v;
lli p = SZ(dist[v]) -1 ;
while(C != -1){
f[C] = min(f[C],dist[v][p--]);
change.PB(C);
C = Par[C];
}
}
void rem(lli v){
lli C = v;
lli p = SZ(dist[v]) -1 ;
while(C != -1){
f[C] =INF;
C = Par[C];
}
}
lli get(lli v){
lli res = INF;
lli C = v;
lli p = SZ(dist[v]) -1 ;
while(C != -1){
res= min(res,dist[v][p--] + f[C]);
C = Par[C];
}
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
lli ans = INF;
FOR(i,S){
add(X[i]);
}
FOR(i,T){
ans= min(ans,get(Y[i]));
}
for(auto i : change)f[i] = INF;
change.clear();
return ans;
}