| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1124041 | hahahaha | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define i64 long long
#define ld long double
#define ull unsigned long long
#define bit(n,i) ((n>>i)&1)
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FOD(i,a,b) for(int i=a; i>=b; i--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define __sumairu__ signed main()
#define die_hard_onimai_fan void seggs()
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
#define brute(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".ans","w",stdout);}
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ai(n) array<int,n>
#define dbg(x) {cout<<#x<<' '<<x<<endl;}
#define dbgF(arr,l,r) {cout<<#arr;FOR(_i,l,r)cout<<' '<<(arr)[_i];cout<<endl;}
#define dbgArr(arr,n) {cout<<#arr;FOR(_i,1,n)cout<<' '<<(arr)[_i];cout<<endl;}
#define el '\n'
template <typename T,typename U>
ostream& operator<<(ostream &os,pair<T,U>p){return os<<"{"<<p.fi<<", "<<p.se<<"}";}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
i64 Rand(i64 l,i64 r)
{
i64 ans=l+rd()%(r-l+1);
assert(l<=ans&&ans<=r);
return ans;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
//const i64 base=1e9+7;
//const i64 mod=(1ll<<53)+5;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#define int long long
#define debug 0
//const int mod=1e9+7;
//const int mod=998244353;
const int inf=1e9;
const i64 infl=1e18;
///check the limits, dummy
const int N=5e5+5;
int n,q;
vector<pii>adj[N];
int in[N],out[N],timer;
int fa[N],sz[N],h[N],top[N],seq[N];
i64 hw[N];
void dfs_sz(int u,int p=0)
{
sz[u]=1;
for(auto&&xx:adj[u])if(xx.fi!=p)
{
int j=xx.fi,w=xx.se;
fa[j]=u;
h[j]=h[u]+1;
hw[j]=hw[u]+w;
dfs_sz(j,u);
sz[u]+=sz[j];
if(sz[j]>sz[adj[u][0].fi])swap(xx,adj[u][0]);
}
}
void dfs_hld(int u,int p=0)
{
in[u]=++timer;
seq[timer]=u;
for(auto&&[j,w]:adj[u])if(j!=p)
{
top[j]=(j==adj[u][0].fi?top[u]:j);
dfs_hld(j,u);
}
out[u]=timer;
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(h[top[u]]>h[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
return h[u]<h[v]?u:v;
}
int jump(int u,int k)
{
int d=h[u]-k;
while(h[top[u]]>d)u=fa[top[u]];
return seq[in[u]-h[u]+d];
}
i64 dist(int x,int y)
{
return hw[x]+hw[y]-2*hw[lca(x,y)];
}
bool vis[N];
int getsz(int u,int p=0)
{
sz[u]=1;
for(auto&&[v,w]:adj[u])if(v!=p&&!vis[v])sz[u]+=getsz(v,u);
return sz[u];
}
int centroid(int u,int S,int p=0)
{
for(auto&&[v,w]:adj[u])if(v!=p&&!vis[v]&&sz[v]>S/2)return centroid(v,S,u);
return u;
}
int par[N];
i64 h2[N];
void decomp(int u,int p=0)
{
u=centroid(u,getsz(u));
vis[u]=1;
par[u]=p;
if(p)h2[u]=h2[p]+dist(u,p);
for(auto&&[v,w]:adj[u])if(v!=p&&!vis[v])decomp(v,u);
}
int X[N],Y[N];
i64 d[N];
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0; i < N - 1; i++){
A[i]++;
B[i]++;
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
h[1]=1;
dfs_sz(1);
top[1]=1;
dfs_hld(1);
decomp(1);
fill(d+1,d+n+1,infl);
}
long long Query(int S, int X[], int T, int Y[]) {
auto paint=[&](int u){
for(int i=u;i;i=par[i])chmin(d[i],h2[u]-h2[i]);
};
auto get=[&](int u){
i64 ans=infl;
for(int i=u;i;i=par[i])
{
chmin(ans,d[i]+h2[u]-h2[i]);
}
return ans;
};
auto reset=[&](int u){
for(int i=u;i;i=par[i])d[i]=infl;
};
FOR(i,0,S-1)X[i]++;
FOR(i,0,T-1)Y[i]++;
FOR(i,1,S)paint(X[i-1]);
i64 ans=infl;
FOR(i,1,T)chmin(ans,get(Y[i-1]));
FOR(i,1,S)reset(X[i-1]);
assert(*min_element(d+1,d+n+1)==*max_element(d+1,d+n+1)&&*min_element(d+1,d+n+1)==infl);
return ans;
}
//die_hard_onimai_fan
//{
// cin>>n>>q;
// FOR(i,2,n)
// {
// int u,v,w;
// cin>>u>>v>>w;
// u++,v++;
// adj[u].pb({v,w});
// adj[v].pb({u,w});
// }
// h[1]=1;
// dfs_sz(1);
// top[1]=1;
// dfs_hld(1);
//
// decomp(1);
// fill(d+1,d+n+1,infl);
//
// auto paint=[&](int u){
// for(int i=u;i;i=par[i])chmin(d[i],h2[u]-h2[i]);
// };
//
// auto get=[&](int u){
// i64 ans=infl;
// for(int i=u;i;i=par[i])
// {
// chmin(ans,d[i]+h2[u]-h2[i]);
// }
// return ans;
// };
//
// auto reset=[&](int u){
// for(int i=u;i;i=par[i])d[i]=infl;
// };
//
// FOR(_,1,q)
// {
// int S,T;
// cin>>S>>T;
//
// FOR(i,1,S)cin>>X[i],X[i]++;
// FOR(i,1,T)cin>>Y[i],Y[i]++;
//
// FOR(i,1,S)paint(X[i]);
//
// i64 ans=infl;
// FOR(i,1,T)chmin(ans,get(Y[i]));
//
// FOR(i,1,S)reset(X[i]);
// assert(*min_element(d+1,d+n+1)==*max_element(d+1,d+n+1)&&*min_element(d+1,d+n+1)==infl);
//
// cout<<ans<<el;
// }
//}
//
//__sumairu__
//{
// FAST
// file("");
//
// int tt=1;//cin>>tt;
// while(tt--)seggs();
// cerr<<"\nTime elapsed: "<<TIME<<" s.\n";
//}
///**
//7 3
//0 1 4
//1 2 4
//2 3 5
//2 4 6
//4 5 5
//1 6 3
//2 2
//0 6
//3 4
//3 2
//0 1 3
//4 6
//1 1
//2
//5
//*/