| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1297987 | trandaihao5555 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#define int long long
#define debug cout << "ok\n";
#define SQR(x) (1LL * ((x) * (x)))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;
using namespace std;
const int M = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);
const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
template<class _, class __>
bool minimize(_ &x, const __ y){
if(x > y){
x = y;
return true;
} else return false;
}
template<class _, class __>
bool maximize(_ &x, const __ y){
if(x < y){
x = y;
return true;
} else return false;
}
template<class _,class __>
void Add(_ &x, const __ y) {
x += y;
if (x >= M) {
x -= M;
}
return;
}
template<class _,class __>
void Diff(_ &x, const __ y) {
x -= y;
if (x < 0) {
x += M;
}
return;
}
//--------------------------------------------------------------
const int MaxN = 5e5+7;
const int Log = 20;
const int can = 710;
int h[MaxN],up[MaxN][Log],n;
ll dist[MaxN],Dist[MaxN];
vector<pii> a[MaxN];
void dfs(int u,int p) {
for (pii e : a[u]) {
int v = e.fi;
int w = e.se;
if (v == p) continue;
h[v] += h[u] + 1;
dist[v] = dist[u] + w;
up[v][0] = u;
for (int i=1;i<Log;i++) up[v][i] = up[up[v][i-1]][i-1];
dfs(v,u);
}
}
int LCA(int u,int v) {
if (h[u] < h[v]) swap(u,v);
for (int i=0;i<Log;i++) if (BIT(h[u]-h[v],i)) u = up[u][i];
if (u == v) return u;
for (int i=Log-1;i>=0;i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int Dist_lca(int u,int v) {
return dist[u] + dist[v] - 2 * dist[LCA(u,v)];
}
void Init(int N,vi A,vi B,vi D) {
n = N;
for (int i=1;i<N;i++) {
int u = A[i-1];
int v = B[i-1];
int w = D[i-1];
a[u].pb(mp(v,w));
a[v].pb(mp(u,w));
}
dfs(1,-1);
}
void Dijkstra(vi lis) {
for (int i=1;i<=n;i++) Dist[i] = INFLL;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
for (int x : lis) {
Dist[x] = 0;
pq.push(mp(0,x));
}
while (!pq.empty()) {
int u = pq.top().se;
ll du = pq.top().fi;
pq.pop();
if (du != Dist[u]) continue;
for (pii e : a[u]) {
int v = e.fi;
int w = e.se;
if (minimize(Dist[v],du + w)) {
pq.push(mp(Dist[v],v));
}
}
}
}
ll Query(int S,vi X,int T,vi Y) {
if (S < T) swap(S,T),swap(X,Y);
if (S > can) {
Dijkstra(X);
ll res = INFLL;
for (int y : Y) minimize(res,Dist[y]);
return res;
}
else {
ll res = INFLL;
for (int x : X) {
for (int y : Y) {
minimize(res,Dist_lca(x,y));
}
}
return res;
}
}
//void sol() {
// int n,q;
// vi U,V,W;
// cin >> n >> q;
// for (int i=1;i<n;i++) {
// int u,v,w;
// cin >> u >> v >> w;
// U.pb(u);
// V.pb(v);
// W.pb(w);
// }
// Init(n,U,V,W);
// for (int i=1;i<=q;i++) {
// int S,T;
// vi X,Y;
// cin >> S >> T;
// X.resize(S);
// Y.resize(T);
// for (int & x : X) cin >> x;
// for (int & y : Y) cin >> y;
// cout << Query(S,X,T,Y) << '\n';
// }
//}
//
//signed main() {
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
// FAST
// int t=1;
// cin >> t;
// while (t--) sol();
//}