Submission #941380

#	Time	Username	Problem	Language	Result	Execution time	Memory
941380		cpptowin	Factories (JOI14_factories)	C++17	0 / 100	18 ms	68264 KiB

factories

#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define inf 1000000000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
long long n,q;
vector<pair<long long,long long>> ke[maxn];
long long minn[maxn];
bool is_remove[maxn];
long long sz[maxn];
vector<pair<long long,long long>> par[maxn];
long long x[maxn],y[maxn];
long long dfs_size(long long u,long long parent = -1)
{
    sz[u] = 1;
    for(auto [v,_] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        sz[u] += dfs_size(v,u);
    }
    return sz[u];
}
long long dfs_centroid(long long u,long long tree_size,long long parent = -1)
{
    for(auto [v,_] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        if(2 * sz[v] > tree_size) return dfs_centroid(v,tree_size,u);
    }
    return u;
}
void dfs_dist(long long u,long long parent,long long centroid,long long cur_len)
{
    for(auto [v,w] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        dfs_dist(v,u,centroid,cur_len + w);
    }
    par[u].pb(cur_len,centroid);
}
void build_centroid(long long u)
{
    long long centroid = dfs_centroid(u,dfs_size(u));
    is_remove[centroid] = 1;
    // do sth
    for(auto [v,w] : ke[centroid])
    {
        if(is_remove[v]) continue;
        dfs_dist(v,centroid,centroid,w);
    }
    for(auto [v,w] : ke[centroid])
    {
        if(is_remove[v]) continue;
        build_centroid(v);
    }
}
void update(long long u)
{
    minn[u] = 0;
    for(auto [dist,centroid] : par[u])
    {
        minn[centroid] = min(minn[centroid],dist);
    }
}
void del(long long u)
{
    minn[u] = inf;
    for(auto [_,centroid] : par[u])
    {
        minn[centroid] = inf;
    }
}
long long get(long long u)
{
    long long ans = minn[u];
    for(auto [dist,centroid] : par[u])
    {
        ans = min(ans,dist + minn[centroid]);
    }
    return ans;
}
void Init(int N, int A[], int B[], int D[])
{
    fo(i,0,N - 2)
    {
        ke[A[i] + 1].pb(B[i] + 1,D[i]);
        ke[B[i] + 1].pb(A[i] + 1,D[i]);
    }
    build_centroid(1);
}
long long Query(int S, int X[], int T, int Y[])
{
    fo(i,0,S - 1) update(X[i] + 1);
    long long res = 1e18;
    fo(i,0,T - 1) res = min(res,get(Y[i] + 1));
    return res;
//    fo(i,0,S - 1) del(X[i] + 1);
}

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