Submission #307551

#	Time	Username	Problem	Language	Result	Execution time	Memory
307551		talant117408	Factories (JOI14_factories)	C++17	100 / 100	4848 ms	194892 KiB

factories

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

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define pb push_back
#define mp make_pair

const int NN = 5e5+7;
vector <vector <pii>> graph(NN);
vector <vector <ll>> dist(NN, vector <ll> (20));
vector <int> saizu(NN), par(NN), vis(NN), lvl(NN);
vector <ll> ans(NN, 2e18);
int timer;
stack <int> st;

void find_size(int v, int p, int l){
    saizu[v] = 1;
    
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p){
            if(l) dist[to.first][l-1] = dist[v][l-1]+to.second;
            find_size(to.first, v, l);
            saizu[v] += saizu[to.first];
        }
    }
}

int find_centroid(int v, int p, int n){
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p && saizu[to.first] > n/2){
            return find_centroid(to.first, v, n);
        }
    }
    return v;
}

void init_centroid(int v = 0, int p = -1, int l = 0){
    find_size(v, -1, l);
    
    int c = find_centroid(v, p, saizu[v]);
    vis[c] = 1;
    par[c] = p;
    lvl[c] = l;
    
    for(auto to : graph[c]){
        if(!vis[to.first]){
            dist[to.first][l] = to.second;
            init_centroid(to.first, c, l+1);
        }
    }
    vis[c] = 0;
}

void Init(int n, int x[], int y[], int w[]){
    for(int i = 0; i < n-1; i++){
        graph[x[i]].pb(mp(y[i], w[i]));
        graph[y[i]].pb(mp(x[i], w[i]));
    }
    init_centroid();
}

void update(int v){
    int x = v, l = lvl[v];
    while(x != -1){
        ans[x] = min(ans[x], dist[v][l]);
        st.push(x);
        x = par[x];
        l--;
    }
}

ll get(int v){
    ll x = v, mn = 2e18, l = lvl[v];
    while(x != -1){
        mn = min(ans[x]+dist[v][l], mn);
        x = par[x];
        l--;
    }
    return mn;
}

long long Query(int s, int x[], int t, int y[]){
    ll mn = 2e18;
    for(int i = 0; i < s; i++)
        update(x[i]);
    for(int i = 0; i < t; i++)
        mn = min(mn, get(y[i]));
    
    while(st.size()){
        ans[st.top()] = 2e18;
        st.pop();
    }
    
    return mn;
}

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