Submission #422555

#	Time	Username	Problem	Language	Result	Execution time	Memory
422555		juggernaut	Factories (JOI14_factories)	C++17	100 / 100	4643 ms	138828 KiB

factories

#pragma GCC optimize("Ofast")
#include"factories.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
template<class T>void umin(T &a,T b){if(b<a)a=b;}
using namespace std;
typedef long long ll;
vector<pair<int,int>>g[500001];
int sz[500001];
bool black[500001];
void build_sz(int v,int p){
    sz[v]=1;
    for(auto &[to,wegiht]:g[v])if(to!=p&&!black[to]){
        build_sz(to,v);
        sz[v]+=sz[to];
    }
}
int get_centroid(int v,int p){
    int siz=sz[v]>>1;
    while(true){
        bool can=true;
        for(auto &[to,weight]:g[v]){
            if(black[to]||to==p)continue;
            if(sz[to]>siz){
                can=false;
                p=v;
                v=to;
                break;
            }
        }
        if(can)return v;
    }
}
ll dist[20][500001];
void build_dist(int v,int p,int lv){
    for(auto &[to,weight]:g[v])if(to!=p&&!black[to]){
        dist[lv][to]=dist[lv][v]+weight;
        build_dist(to,v,lv);
    }
}
int parent[500001];
int level[500001];
ll mn[500001];
int n;
void decompose(int centroid,int parent_centroid){
    build_sz(centroid,0);
    centroid=get_centroid(centroid,0);
    parent[centroid]=parent_centroid;
    level[centroid]=level[parent_centroid]+1;
    build_dist(centroid,0,level[centroid]);
    black[centroid]=true;
    for(auto &[to,weight]:g[centroid])if(!black[to])decompose(to,centroid);
}
void Init(int n,int a[],int b[],int c[]){
    ::n=n;
    for(int i=0;i<n-1;i++){
        int &x=a[i];
        int &y=b[i];
        int &z=c[i];
        g[x+1].emplace_back(y+1,z);
        g[y+1].emplace_back(x+1,z);
    }
    level[0]=-1;
    decompose(1,0);
    for(int i=1;i<=n;i++)mn[i]=1e15;
}
ll Query(int s,int x[],int t,int y[]){
    for(int i=0;i<s;i++){
        int ver=x[i]+1;
        while(ver){
            umin(mn[ver],dist[level[ver]][x[i]+1]);
            ver=parent[ver];
        }
    }
    ll ans=1e15;
    for(int i=0;i<t;i++){
        int ver=y[i]+1;
        while(ver){
            umin(ans,mn[ver]+dist[level[ver]][y[i]+1]);
            ver=parent[ver];
        }
    }
    for(int i=0;i<s;i++){
        int ver=x[i]+1;
        while(ver){
            mn[ver]=1e15;
            ver=parent[ver];
        }
    }
    return ans;
}

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