Submission #589624

#	Time	Username	Problem	Language	Result	Execution time	Memory
589624		gg123_pe	Factories (JOI14_factories)	C++14	33 / 100	8042 ms	205332 KiB

factories

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

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

#define ff first 
#define ss second 

const int N = 5e5 + 5; 
const ll inf = 1e17 + 100; 


int n, p[N], sz[N], LVL[N];
ll h[N][20]; 
bool vis[N]; 
multiset <ll> s[N];  
vector <ii> adj[N]; 

int size(int u, int f){
    sz[u] = 1; 
    for(auto p: adj[u]){
        if(p.ff != f and !vis[p.ff]) sz[u] += size(p.ff, u); 
    }
    return sz[u]; 
}

int get_centroid(int u, int f, int curr_size){
    for(auto p: adj[u]) if(p.ff != f and !vis[p.ff] and sz[p.ff]*2 > curr_size) 
        return get_centroid(p.ff, u, curr_size);
    return u; 
}

void dfs(int u, int f, int lvl){
    for(auto p: adj[u]){
        ll v = p.ff, w = p.ss; 
        if(vis[v] or v == f) continue; 
        h[v][lvl] = h[u][lvl] + w; 
        dfs(v, u, lvl); 
    }
}
void descompose(int u, int f, int lvl){
    int cen = get_centroid(u, f, size(u, f));
    vis[cen] = 1; 

    LVL[cen] = ++lvl; 
    p[cen] = f, h[cen][lvl] = 0; 
    dfs(cen, f, lvl); 

    for(auto p: adj[cen]) if(!vis[p.ff]) descompose(p.ff, cen, lvl); 
}
void Init(int ni, int a[], int b[], int d[]){
    n = ni; 

    f(i,0,n-1){
        adj[a[i]].push_back({b[i], d[i]}); 
        adj[b[i]].push_back({a[i], d[i]}); 
    }
    descompose(0, -1, 0); 
}

void paint_red(int u){
    int aux = u; 
    while(u != -1){
        s[u].insert(h[aux][LVL[u]]); 
        u = p[u]; 
    }
}

void paint_white(int u){
    int aux = u; 
    while(u != -1){
        auto it = s[u].find(h[aux][LVL[u]]); 
        s[u].erase(it); 
        u = p[u];
    }
}

ll get(int u){
    ll ans = inf, aux = u; 
    
    while(u != -1){
        if(s[u].size()){
            ans = min(ans, h[aux][LVL[u]] + *s[u].begin()); 
        }
        u = p[u]; 
    }
    return ans; 
}
ll Query(int S, int X[], int T, int Y[]){
    f(i,0,S) paint_red(X[i]); 
    ll ans = inf; 

    f(i,0,T) ans = min(ans, get(Y[i])); 
    f(i,0,S) paint_white(X[i]); 
    return ans; 
}

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