Submission #906103

#	Time	Username	Problem	Language	Result	Execution time	Memory
906103		a_l_i_r_e_z_a	Factories (JOI14_factories)	C++17	100 / 100	5359 ms	361436 KiB

factories

// In the name of God

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 5e5 + 5;
const ll inf = 1e18 + 7;
int n, q, sz[maxn];
ll dist[maxn];
vector<pll> adj[maxn];
vector<pll> par[maxn];
bool mark[maxn];

void get_sz(int v, int p = -1){
    sz[v] = 1;
    for(auto [u, w]: adj[v]){
        if(u != p && !mark[u]){
            get_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

int find(int v, int s, int p = -1){
    for(auto [u, w]: adj[v]) if(u != p && !mark[u] && sz[u] * 2 > s) return find(u, s, v);
    return v;
}

void dfs(int v, int center, ll h = 0, int p = -1){
    par[v].pb(mp(center, h));
    for(auto [u, w]: adj[v]){
        if(!mark[u] && u != p) dfs(u, center, h +  w, v);
    }
}

void centroid_decomp(int v = 0){
    get_sz(v);
    v = find(v, sz[v]);
    dfs(v, v);
    mark[v] = 1;
    for(auto [u, w]: adj[v]) if(!mark[u]) centroid_decomp(u);
}

void turnOff(int v){
    for(auto [p, d]: par[v]) dist[p] = inf;
}

void turnOn(int v){
    for(auto [p, d]: par[v]) smin(dist[p], d);
}

ll get(int v){
    ll res = inf;
    for(auto [p, d]: par[v]) smin(res, d + dist[p]);
    return res;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    fill(dist, dist + n, inf);
    for(int i = 0; i < n - 1; i++){
        int u = A[i], v = B[i], w = D[i];
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    centroid_decomp();
}

ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++) turnOn(X[i]);
    ll ans = inf;
    for(int i = 0; i < T; i++) smin(ans, get(Y[i]));
    for(int i = 0; i < S; i++) turnOff(X[i]);
    return ans;
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, q; cin >> n >> q;
//     fill(dist, dist + n, inf);
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         adj[u].pb(mp(v, w));
//         adj[v].pb(mp(u, w));
//     }
//     centroid_decomp();
//     while(q--){
//         int S, T; cin >> S >> T;
//         for(int i = 0; i < S; i++){
//             cin >> a[i];
//             turnOn(a[i]);
//         }
//         ll ans = inf;
//         for(int i = 0; i < T; i++){
//             int v; cin >> v;
//             smin(ans, get(v));
//         }
//         for(int i = 0; i < S; i++) turnOff(a[i]);
//         cout << ans << '\n';
//     }

//     return 0;
// }

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