Submission #445182

#	Time	Username	Problem	Language	Result	Execution time	Memory
445182		JovanB	Factories (JOI14_factories)	C++17	100 / 100	5762 ms	261312 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
const ll INF = 1000000000000000000LL;
 
const int MAXN = 500000;
 
vector <pair <int, int>> graf[MAXN+5];
pair <int, ll> parents[MAXN+5][20];
int dokle[MAXN+5];
 
bool erased[MAXN+5];
int sz[MAXN+5];
ll mnd[MAXN+5];
 
void dfs_size(int v, int p){
    sz[v] = 1;
    for(auto c : graf[v]){
        if(erased[c.first] || c.first == p) continue;
        dfs_size(c.first, v);
        sz[v] += sz[c.first];
    }
}
 
int find_centroid(int v, int p, int svi){
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > svi) return find_centroid(c.first, v, svi);
    return v;
}
 
void dfs_depth(int v, int p, ll dst, int root){
    parents[v][++dokle[v]] = {root, dst};
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p) dfs_depth(c.first, v, dst + c.second, root);
}
 
void decompose(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        dfs_size(v, 0);
        v = find_centroid(v, 0, sz[v]);
        dfs_depth(v, 0, 0, v);
        erased[v] = 1;
        for(auto c : graf[v]) if(!erased[c.first]) q.push(c.first);
    }
}
 
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N-1; i++){
        A[i]++;
        B[i]++;
        graf[A[i]].push_back({B[i], D[i]});
        graf[B[i]].push_back({A[i], D[i]});
    }
    decompose();
    for(int i=1; i<=N; i++) reverse(parents[i]+1, parents[i]+1+dokle[i]);
    for(int i=1; i<=N; i++) mnd[i] = INF;
}
 
void upd(int x){
    for(int i=1; i<=dokle[x]; i++) if(mnd[parents[x][i].first] > parents[x][i].second) mnd[parents[x][i].first] = parents[x][i].second;
}
 
void brisi(int x){
    for(int i=1; i<=dokle[x]; i++){
        pair <int, ll> c = parents[x][i];
        if(mnd[c.first] == INF) return;
        mnd[c.first] = INF;
    }
}
 
ll query(int x){
    ll res = INF;
    for(int i=1; i<=dokle[x]; i++) res = min(res, parents[x][i].second + mnd[parents[x][i].first]);
    return res;
}
 
long long Query(int S, int X[], int T, int Y[]) {
    ll mn = INF;
    if(S < T){
        for(int i=0; i<S; i++) upd(X[i]+1);
        for(int i=0; i<T; i++) mn = min(mn, query(Y[i]+1));
        for(int i=0; i<S; i++) brisi(X[i]+1);
    }
    else{
        for(int i=0; i<T; i++) upd(Y[i]+1);
        for(int i=0; i<S; i++) mn = min(mn, query(X[i]+1));
        for(int i=0; i<T; i++) brisi(Y[i]+1);
    }
    return mn;
}

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