Submission #1258870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258870		khoavn2008	Factories (JOI14_factories)	C++20	0 / 100	16 ms	24132 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define REP(i,r) for(ll i=0,_r=(r);i<_r;i++)
#define FOR(i,l,r) for(ll i=(l),_r=(r);i<=_r;i++)
#define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define FORNG(i,r,l) for(ll i=(r),_l=(l);i>=_l;i--)
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1LL)
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())

const ll MOD = 1e9+7, N = 5e5+10, INF = 1e18, LOG = 20;
ll n,q,d[N],sz[N];
vector<pair<ll,ll>> adj[N],cen_par[N];
bool del[N];
ll get_sz(ll u,ll par = -1){
    sz[u] = 1;
    for(auto [v, w] : adj[u]){
        if(v == par || del[v])continue;
        sz[u] += get_sz(v, u);
    }
    return sz[u];
}
ll find_centroid(ll u,ll par,ll cur_sz){
    for(auto [v, w] : adj[u]){
        if(v == par || del[v])continue;
        if(sz[v] * 2 > cur_sz)return find_centroid(v, u, cur_sz);
    }
    return u;
}
void dfs(ll u,ll par,ll cen,ll high){
    cen_par[u].pb({cen, high});
    for(auto [v, w] : adj[u]){
        if(v == par || del[v])continue;
        dfs(v, u, cen, high + w);
    }
}
void centroid_dcp(ll u){
    ll root = find_centroid(u, -1, get_sz(u));
    del[root] = 1;
    dfs(root, -1, root, 0);
    for(auto [v, w] : adj[root])if(!del[v])centroid_dcp(v);
}
ll Query(int s,int x[],int t,int y[]){
    ll res = INF;
    REP(i, s){
        ll u = x[i];
        for(auto [cen, dist] : cen_par[u]){
            d[cen] = min(d[cen], dist);
        }
    }
    REP(i, t){
        ll u = y[i];
        for(auto [cen, dist] : cen_par[u]){
            res = min(res, dist + d[cen]);
        }
    }
    REP(i, s){
        ll u = x[i];
        for(auto [cen, dist] : cen_par[u]){
            d[cen] = INF;
        }
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]){
    n = N;
    REP(i,n)adj[A[i]].pb({B[i], D[i]}),adj[B[i]].pb({A[i], D[i]});
    centroid_dcp(0);
}

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