Submission #993828

#	Time	Username	Problem	Language	Result	Execution time	Memory
993828		Albertstein	Factories (JOI14_factories)	C++17	100 / 100	2867 ms	356848 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 500001, INF = LLONG_MAX / 3;
bool rem[maxn];
int sub_sz[maxn];
long long mini[maxn];
vector <pair<int, long long> > Dist[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

void dfs2(int u, int p, long long dist, int r){
    Dist[u].push_back({r, dist});
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            dfs2(v, u, dist + d, r);
        }
    }
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int sz = dfs(r);
    int c = g_cen(r, sz);
    dfs2(c, -1, 0, c);
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            sol(v);
        }
    }
    return c;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    for(int i = 0; i < N; i++) {mini[i] = INF;}
    sol();
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    vector <int> q;
    for(int i = 0; i < S; i++){
        int x = X[i];
        for(auto [v, d] : Dist[x]){
            mini[v] = min(mini[v], d);
            q.push_back(v);
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        for(auto [v, d] : Dist[y]){
            ans = min(ans, mini[v] + d);
        }
    }//*/
    for(auto x : q) {mini[x] = INF;}
    return ans;
}

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