Submission #728026

#	Time	Username	Problem	Language	Result	Execution time	Memory
728026		Seb	Factories (JOI14_factories)	C++17	0 / 100	68 ms	96348 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;
vector <pair<ll,ll>> g[MAXN];
vector <ll> h[MAXN];
set <ll> st[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) {
    ll aux = nodo;
    while (aux!=0) {
        st[aux].clear();
        aux = centro[aux];
    }
    return;
}

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

void query(ll nodo) {
    ll aux = nodo, cnt = 0;
    if (!h[nodo].empty()) cnt = h[nodo].size()-1;
    while (aux!=0) {
        if (!st[aux].empty()) {
            ans = min(ans,*(st[aux].begin()) + h[nodo][cnt]);
        }
        aux = centro[aux];
        cnt--;
    }
    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);
    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(Y[i]+1);
    for (int i=0;i<S;i++) limpia(X[i]+1);
    return ans;
}

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