Submission #1281794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281794		dhuyyyy	Factories (JOI14_factories)	C++20	100 / 100	2674 ms	350772 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
//#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 5e5+5;

int n, m, u, v, x, root;

int sz[N];

long long res, c, dist[N];

bool num[N];

vector <pair<int,long long>> adj[N], anc[N];

void getSize(int u,int p){
    sz[u] = 1;
    for (pair<int, long long> it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        getSize(it.fi,u);
        sz[u] += sz[it.fi];
    }
}
int getCentroid(int u,int p,int n){
    for (pair<int, long long> it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        if (sz[it.fi] * 2 > n) return getCentroid(it.fi,u,n);
    }
    return u;
}
void dfs(int u,int p,int root,long long length){
    anc[u].push_back({root,length});
    for (pair<int, long long> it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        dfs(it.fi,u,root,length + it.se);
    }
}
void decompose(int u){
    getSize(u,0);
    m = sz[u];
    root = getCentroid(u,0,m);
    num[root] = 1;
    for (pair<int,long long> it : adj[root]){
        if (num[it.fi]) continue;
        dfs(it.fi,root,root,it.se);
    }
    for (pair<int,long long> it : adj[root]){
        if (num[it.fi]) continue;
        decompose(it.fi);
    }
}
void update(int u,int type){
    for (pair<int,long long> it : anc[u]){
        if (type) dist[it.fi] = 1e18;
        else dist[it.fi] = min(dist[it.fi],it.se);
    }
}
void get(int u){
    for (pair<int, long long> it : anc[u]){
        res = min(res,dist[it.fi] + it.se);
    }
}
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for (int i = 0; i < n - 1; i++){
        u = A[i] + 1;
        v = B[i] + 1;
        c = D[i];
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    for (int i = 1; i <= n; i++){
         dist[i] = 1e18;
         anc[i].push_back({i,0});
    }
    decompose(1);
}

long long Query(int S, int X[], int T, int Y[]){
    res = 1e18;
    for (int i = 0; i < S; i++) X[i]++;
    for (int i = 0; i < T; i++) Y[i]++;
    for (int i = 0; i < S; i++) update(X[i],0);
    for (int i = 0; i < T; i++) get(Y[i]);
    for (int i = 0; i < S; i++) update(X[i],1);
    return res;
}

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