Submission #433417

#	Time	Username	Problem	Language	Result	Execution time	Memory
433417		jovan_b	Factories (JOI14_factories)	C++17	100 / 100	6948 ms	239828 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];
pair <int, ll> parents[MAXN+5][20];
int dokle[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][++dokle[v]] = {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]+1, parents[i]+1+dokle[i]);
    for(int i=1; i<=N; i++) mnd[i] = INF;
}

void upd(int x){
    for(int i=1; i<=dokle[x]; i++) if(mnd[parents[x][i].first] > parents[x][i].second) mnd[parents[x][i].first] = parents[x][i].second;
}

void brisi(int x){
    for(int i=1; i<=dokle[x]; i++){
        pair <int, ll> c = parents[x][i];
        if(mnd[c.first] == INF) return;
        mnd[c.first] = INF;
    }
}

ll query(int x){
    ll res = INF;
    for(int i=1; i<=dokle[x]; i++) res = min(res, parents[x][i].second + mnd[parents[x][i].first]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = INF;
    if(S < T){
        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);
    }
    else{
        for(int i=0; i<T; i++) upd(Y[i]+1);
        for(int i=0; i<S; i++) mn = min(mn, query(X[i]+1));
        for(int i=0; i<T; i++) brisi(Y[i]+1);
    }
    return mn;
}

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