Submission #1000296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000296		MarwenElarbi	Factories (JOI14_factories)	C++17	100 / 100	2904 ms	351660 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=5e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int>> adj[nax];
int sz[nax];
bool removed[nax];
vector<pair<int,ll>> parent[nax];
long long ans[nax];
int get_sz(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        sz[x]+=get_sz(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz) return get_centroid(u.fi,t_sz,x);
    }
    return x;
}
void get_dist(int x,int centroid,int p,long long cur){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        cur+=u.se;
        get_dist(u.fi,centroid,x,cur);
        cur-=u.se;
    }
    parent[x].pb({centroid,cur});
    return;
}
void build(int x){
    int centroid=get_centroid(x,get_sz(x,-1),-1);
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        get_dist(u.fi,centroid,centroid,u.se);
    }
    removed[centroid]=1;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi);
    }
    return;
}
void paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=min(ans[u.fi],u.se);
    }
    ans[x]=0;
    return;
}
void init_paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=1e18;
    }
    ans[x]=1e18;
    return;
}
long long get_ans(int x){
    ll res=ans[x];
    for(auto u:parent[x]){
        res=min(res,u.se+ans[u.fi]);
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    int n=N;
    for (int i = 0; i < n; ++i) ans[i]=1e18;
    for (int i = 0; i < n-1; ++i)
    {
        adj[A[i]].pb({B[i],D[i]});
        adj[B[i]].pb({A[i],D[i]});
    }
    build(0);
    return;
}
long long Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < T; ++i)
    {
        paint(Y[i]);
    }
    ll res=1e18;
    for (int i = 0; i < S; ++i)
    {
        res=min(res,get_ans(X[i]));
    }
    for (int i = 0; i < T; ++i)
    {
        init_paint(Y[i]);
    }
    return res;
}

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