제출 #1161038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161038		hainam2k9	Factories (JOI14_factories)	C++20	100 / 100	2670 ms	358788 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 5e5+5;
const string NAME = "";
int n,sz[MAXN];
ll dist[MAXN];
bool del[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<pair<int,ll>> centroid[MAXN];
void GetSize(int u, int par){
    sz[u]=1;
    for(pair<int,int>& v : adj[u])
        if(!del[v.fi]&&v.fi!=par) GetSize(v.fi,u), sz[u]+=sz[v.fi];
}
int Centroid(int u, int par, const int& N){
    for(pair<int,int>& v : adj[u])
        if(!del[v.fi]&&v.fi!=par&&sz[v.fi]>N>>1) return Centroid(v.fi,u,N);
    return u;
}
void dfs(const int& root, int u, int par, ll dist){
    centroid[u].pb(root,dist);
    for(pair<int,int>& v : adj[u])
        if(!del[v.fi]&&v.fi!=par) dfs(root,v.fi,u,dist+v.se);
}
void CentroidDecomposition(int u){
    GetSize(u,0);
    int root=Centroid(u,0,sz[u]);
    centroid[root].pb(root,0);
    for(pair<int,int>& v : adj[root])
        if(!del[v.fi]) dfs(root,v.fi,root,v.se);
    del[root]=1;
    for(pair<int,int>& v : adj[root])
        if(!del[v.fi]) CentroidDecomposition(v.fi);
}
void Init(int N, int a[], int b[], int d[]){
    n=N;
    for(int i = 0; i<n; ++i)
        ++a[i], ++b[i], adj[a[i]].pb(b[i],d[i]), adj[b[i]].pb(a[i],d[i]);
    memset(dist,0x3f,sizeof(dist));
    CentroidDecomposition(1);
}
ll Query(int n, int a[], int m, int b[]){
    ll rs=1e18;
    for(int i = 0; i<n; ++i){
        ++a[i];
        for(pair<int,ll>& p : centroid[a[i]])
            dist[p.fi]=min(dist[p.fi],p.se);
    }
    for(int i = 0; i<m; ++i){
        ++b[i];
        for(pair<int,ll>& p : centroid[b[i]])
            rs=min(rs,dist[p.fi]+p.se);
    }
    for(int i = 0; i<n; ++i){
        for(pair<int,ll>& p : centroid[a[i]])
            dist[p.fi]=1e18;
    }
    return rs;
}

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