Submission #307544

#	Time	Username	Problem	Language	Result	Execution time	Memory
307544		talant117408	Factories (JOI14_factories)	C++17	15 / 100	8035 ms	121892 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 <int>> up(NN);
vector <int> tin(NN), tout(NN), saizu(NN), par(NN), vis(NN);
vector <ll> ans(NN, 2e18), dist(NN);
int timer;
stack <int> st;

void dfs(int v, int p = 0){
    tin[v] = ++timer;
    up[v][0] = p;
    for(int i = 1; i < 20; i++){
        up[v][i] = up[up[v][i-1]][i-1];
    }
    for(auto to : graph[v]){
        if(to.first != p){
            dist[to.first] = dist[v]+to.second;
            dfs(to.first, v);
        }
    }
    
    tout[v] = ++timer;
} 

bool upper(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b){
    if(upper(a, b)) return a;
    if(upper(b, a)) return b;
    for(int i = 19; i >= 0; i--){
        if(!upper(up[a][i], b)){
            a = up[a][i];
        }
    }
    return up[a][0];
}

ll getdist(int a, int b){
    return dist[a]+dist[b]-2*dist[lca(a, b)];
}

void find_size(int v, int p = -1){
    saizu[v] = 1;
    
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p){
            find_size(to.first, v);
            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){
    find_size(v);
    
    int c = find_centroid(v, p, saizu[v]);
    vis[c] = 1;
    par[c] = p;
    
    for(auto to : graph[c]){
        if(!vis[to.first]){
            init_centroid(to.first, c);
        }
    }
    vis[c] = 0;
}

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

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

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

long long Query(int s, int x[], int t, int y[]){
    int i;
    for(i = 0; i < s; i++){
        update(x[i]);
    }
    
    ll mn = 2e18;
    
    for(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: 0 / 18
• Subtask 3: 0 / 67