Submission #116475

#	Time	Username	Problem	Language	Result	Execution time	Memory
116475		YazanZk	Factories (JOI14_factories)	C++14	33 / 100	8036 ms	227804 KiB

factories

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 5 * 1e5 + 1 ;
const ll inf = 1e18 ;

int n ;
vector < pair < int, int > > G[N];
int sub[N], p[N] , par[N];
bool blocked[N];

void get_size(int u, int pa) {
    p[u] = pa ;
    sub[u] = 1 ;
    for(auto e : G[u]) {
        int v = e.first ;
        if(v == pa || blocked[v])
            continue ;
        get_size(v, u);
        sub[u] += sub[v];
    }
}

vector < ll > dis[N];

void solve(int u , int p , ll d){
     for(auto e : G[u]){
          int v = e.first , w = e.second ;
          if(v == p || blocked[v]) continue ;
          dis[v].push_back(d + w);
          solve(v , u , d + w);
     }
}

int get_centroid(int src) {

    get_size(src, src);

    int centroid = src, best = sub[src] ;
    queue < int > Q ;
    Q.emplace(src);

    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();

        int size = sub[src] - sub[u];
        for(auto e : G[u]) {
            int v = e.first;
            if(v == p[u] || blocked[v])
                continue ;
            Q.emplace(v);
            size = max(size, sub[v]);
        }

        if(best > size) {
            best = size;
            centroid = u ;
        }
    }

    blocked[centroid] = true;

    solve(centroid , centroid , 0);

    for(auto e : G[centroid]) {
        int v = e.first ;
        if(blocked[v]) continue ;
        int child = get_centroid(v);
        par[child] = centroid ;
    }

    return centroid ;
}

ll ans[N];
int vis[N];
int t = 1 ;

inline void update(int &u) {
    int v = u ;
    int i = dis[u].size() - 1;
    while(true) {

        if(vis[v] != t)
            vis[v] = t , ans[v] = inf ;

        ans[v] = min(ans[v], dis[u][i]);
        if(v == par[v]) break ;
        v = par[v];
        i--;
    }
}

inline ll query(int &u) {
    int v = u;
    ll ret = inf ;
    int i = dis[u].size() - 1 ;
    while(true) {

        if(vis[v] != t)
            vis[v] = t , ans[v] = inf ;

        ret = min(ret, ans[v] + dis[u][i]);
        if(v == par[v]) break ;
        v = par[v];
        i-- ;
    }
    return ret;
}


ll Query(int S, int X[], int T, int Y[]) {

    t++ ;

    for(int i = 0 ; i < T ; i++) {
        update(Y[i]);
    }

    ll ret = inf ;
    for(int i = 0 ; i < S ; i++) {
        ret = min(ret,  query(X[i]));
    }

    return ret;
}

void Init(int N, int A[], int B[], int D[]) {

    n = N ;
    for(int i = 0 ; i < n - 1 ; i++) {
        int u = A[i], v = B[i], w = D[i];
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    int root = get_centroid(0);
    par[root] = root;

    for(int i = 0 ; i < n ; i++) dis[i].push_back(0);
}

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