제출 #1124075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124075		hahahaha	공장들 (JOI14_factories)	C++20	0 / 100	16 ms	12356 KiB

factories

#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 i64 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 M=5e5+5;

int n,q;
vector<pii>adj[M];

int in[M],out[M],timer;
int fa[M],sz[M],h[M],top[M],seq[M];
i64 hw[M];

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[M];
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[M];
i64 h2[M];
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);
//        cout<<p<<' '<<u<<' '<<h2[u]-h2[p]<<el;
//    }

    for(auto&&[v,w]:adj[u])if(v!=p&&!vis[v])decomp(v,u);
}

i64 d[M];

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],dist(u,i));
    };

    auto get=[&](int u){
        i64 ans=infl;
        for(int i=u;i;i=par[i])
        {
            chmin(ans,d[i]+dist(u,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],dist(u,i));
//    };
//
//    auto get=[&](int u){
//        i64 ans=infl;
//        for(int i=u;i;i=par[i])
//        {
//            chmin(ans,d[i]+dist(u,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("cum");
//
//    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
//*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67