| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 335756 | ec1117 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define bk back()
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define For(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rof(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define nl '\n'
const int MOD = 1e9+7;
const ll INF = 1e18;
const int MX = 3e5+5;
const ld PI = acos((ld)-1);
mt19937 rng; // or mt19937_64
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
template<int SZ> struct Centroid{
vpi adj[SZ];
int lev[SZ], sub[SZ], par[SZ];
ll dist[32][SZ], stor[SZ], anc[32][SZ], ans[SZ];//todo anc
bool done[SZ];
vpi cur;
void ae(int a, int b, int c){
adj[a].pb(mp(b,c));
adj[b].pb(mp(a,c));
}
void dfs(int x, int p){
sub[x]=1;
// int mx=0;
trav(y,adj[x])if(y.f!=p && !done[y.f]){
par[y.f]=x;
dbg(x,y.f);
dfs(y.f,x);
sub[x]+=sub[y.f];
// mx=max(mx,sub[y.f]);
}
// cur.pb(mp(mx,x));
}
int getCen(int x){
// cur.clear();
// dfs(x,x);
// trav(y,cur){
// dbg(x,y.f,y.s);
// if(max(y.f,sub[x]-y.f)*2<=sub[x])
// return y.s;
// }
// assert(false);
dfs(x,x);
int sz = sub[x];
while (1) {
pi mx = {0,0};
for (pi i: adj[x]) if (!done[i.f] && i.f != par[x]) mx = max(mx,{sub[i.f],i.f});
if (mx.f*2 > sz) x = mx.s;
else return x;
}
}
void genDist(int n, int par,int lev, ll d, int dad){
dist[lev][n]=d;
anc[lev][n]=dad;
trav(x,adj[n])if(x.f!=par){
genDist(x.f,n,lev,d+x.s,dad);
}
}
void gen(int CEN, int x){//CEN is prev cen
x=getCen(x);done[x]=1;
dbg(x);
lev[x]=(CEN==-1?0:lev[CEN]+1);
genDist(x,x,lev[x],0,x);
trav(y,adj[x])if(!done[y.f])gen(x,y.f);
}
void init(int N){
For(i,N)done[i]=false;
For(i,N)stor[i]=INF;
gen(-1,0);
}
void upd(int v, int t=1){
// For(i,lev[n]+1){
// if(t==1)ckmin(stor[anc[i][n]],dist[i][n]);
// else stor[anc[i][n]]=INF;
// }
for (int V = v, ind = tmp[v]-1; V >= 0; V = cen[V], ind --) {
// cout << "OH " << v << " " << V << " " << x << "\n";
if (x == 1) ans[V] = min(ans[V],dist[v][ind]);
else ans[V] = INF;
}
}
ll query(int v){
// ll mn=INF;
// For(i,lev[n]+1){
// ckmin(mn, dist[i][n]+stor[anc[i][n]]);
// }
// return mn;
ll ret = INF;
for (int V = v, ind = tmp[v]-1; V >= 0; V = cen[V], ind --) {
// cout << "AH " << V << " " << v << "\n";
ret = min(ret,ans[V]+dist[v][ind]);
}
return ret;
}
};
Centroid<MX> C;
void Init(int N, int A[], int B[], int D[]){
For(i,N-1){
C.ae(A[i],B[i],D[i]);
}
C.init(N);
}
ll Query(int S, int X[], int T, int Y[]){
ll mn=INF;
For(i,S)C.upd(X[i]);
For(i,T)ckmin(mn,C.query(Y[i]));
For(i,S)C.upd(X[i],-1);
return mn;
}
// int main(){
// int n,q;cin>> n>>q;
// int a[n],b[n],d[n];
// For(i,n-1){
// cin>>a[i];
// cin>>b[i];
// cin>>d[i];
// }
// dbg("HI");
// Init(n,a,b,d);
// }