제출 #728038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728038		Seb	공장들 (JOI14_factories)	C++17	100 / 100	3581 ms	245244 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 5e5 + 5;
const ll INF = 1e16;

#define f first
#define s second

ll centro[MAXN],sz[MAXN],ans,st[MAXN];
vector <pair<ll,ll>> g[MAXN];
vector <ll> h[MAXN];
bool vis[MAXN];

void dfs(ll nodo, ll p, ll height, ll caso) {
    if (caso!=0) h[nodo].push_back(height);
    sz[nodo] = 1;
    for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
        if (it->f!=p && vis[it->f]==false) {
            dfs(it->f,nodo,height + it->s,caso);
            sz[nodo] += sz[it->f];
        }
    }
    return;
}

ll find_centro(ll nodo, ll p, ll tot) {
    for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
        if (it->f!=p && vis[it->f]==false && sz[it->f]*2>tot) {
            return find_centro(it->f,nodo,tot);
        }
    }
    return nodo;
}

void decomp(ll nodo, ll p, ll pre) {
    nodo = find_centro(nodo,p,sz[nodo]);
    vis[nodo] = true;
    centro[nodo] = pre;
    for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
        if (vis[it->f]==false) {
            dfs(it->f,nodo,it->s,1);
            decomp(it->f,nodo,nodo);
        }
    }
    return;
}

void limpia(ll nodo) {
    while (nodo!=0) {
        st[nodo] = INF;
        nodo = centro[nodo];
    }
    return;
}

void update(ll nodo) {
    ll aux = centro[nodo], cnt = 0;
    if (!h[nodo].empty()) cnt = h[nodo].size()-1;
    st[nodo] = 0;
    while (aux!=0) {
        st[aux] = min(h[nodo][cnt],st[aux]);
        cnt--;
        aux = centro[aux];
    }
    return;
}

void query_centro(ll nodo) {
    ll aux = centro[nodo], cnt = 0;
    if (!h[nodo].empty()) cnt = h[nodo].size()-1;
    ans = min(ans,st[nodo]);
    while (aux!=0) {
        ans = min(ans,st[aux]+h[nodo][cnt]);
        cnt--;
        aux = centro[aux];
    }
    return;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i=0;i<N-1;i++) {
        g[A[i]+1].push_back({B[i]+1,D[i]});
        g[B[i]+1].push_back({A[i]+1,D[i]});
    }
    dfs(1,0,0,0);
    decomp(1,0,0);
    for (int i=0;i<=N;i++) st[i] = INF;
    return;
}

long long Query(int S, int X[], int T, int Y[]) {
    if (S>T) {
        swap(S,T);
        swap(X,Y);
    }
    ans = INF;
    for (int i=0;i<S;i++) update(X[i]+1);
    for (int i=0;i<T;i++) query_centro(Y[i]+1);
    for (int i=0;i<S;i++) limpia(X[i]+1);
    return ans;
}

/*
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q,S,T;
cin>>n>>q;
int A[n-1],B[n-1],D[n-1];
for (int i=0;i<n-1;i++) {
    cin>>A[i]>>B[i]>>D[i];
}
Init(n,A,B,D);
while (q--) {
    cin>>S>>T;
    int X[S],Y[T];
    for (int i=0;i<S;i++) cin>>X[i];
    for (int i=0;i<T;i++) cin>>Y[i];
    cout<<Query(S,X,T,Y)<<'\n';
}
return 0;
}
*/

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