Submission #433407

#	Time	Username	Problem	Language	Result	Execution time	Memory
433407		jovan_b	Factories (JOI14_factories)	C++17	33 / 100	8109 ms	363780 KiB

factories

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

using namespace std;

using ll = long long;

const ll INF = 1000000000000000000LL;

const int MAXN = 500000;

vector <pair <int, int>> graf[MAXN+5];
vector <pair <int, ll>> parents[MAXN+5];

bool erased[MAXN+5];
int sz[MAXN+5];
ll mnd[MAXN+5];

void dfs_size(int v, int p){
    sz[v] = 1;
    for(auto c : graf[v]){
        if(erased[c.first] || c.first == p) continue;
        dfs_size(c.first, v);
        sz[v] += sz[c.first];
    }
}

int find_centroid(int v, int p, int svi){
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > svi) return find_centroid(c.first, v, svi);
    return v;
}

void dfs_depth(int v, int p, ll dst, int root){
    parents[v].push_back({root, dst});
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p) dfs_depth(c.first, v, dst + c.second, root);
}

void decompose(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        dfs_size(v, 0);
        v = find_centroid(v, 0, sz[v]);
        dfs_depth(v, 0, 0, v);
        erased[v] = 1;
        for(auto c : graf[v]) if(!erased[c.first]) q.push(c.first);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N-1; i++){
        A[i]++;
        B[i]++;
        graf[A[i]].push_back({B[i], D[i]});
        graf[B[i]].push_back({A[i], D[i]});
    }
    decompose();
    for(int i=1; i<=N; i++) reverse(parents[i].begin(), parents[i].end());
    for(int i=1; i<=N; i++) mnd[i] = INF;
}

void upd(int x){
    for(auto c : parents[x]) mnd[c.first] = min(mnd[c.first], c.second);
}

void brisi(int x){
    for(auto c : parents[x]){
        if(mnd[c.first] == INF) break;
        mnd[c.first] = INF;
    }
}

ll query(int x){
    ll res = INF;
    for(auto c : parents[x]) res = min(res, c.second + mnd[c.first]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = INF;
    for(int i=0; i<S; i++) upd(X[i]+1);
    for(int i=0; i<T; i++) mn = min(mn, query(Y[i]+1));
    for(int i=0; i<S; i++) brisi(X[i]+1);
    return mn;
}

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