Submission #1238995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238995		denislav	Factories (JOI14_factories)	C++20	100 / 100	2911 ms	348084 KiB

factories

# include <iostream>
# include <vector>
# include <map>
using namespace std;
# include "factories.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=5e5+11;

int n;
vector<pair<int,long long>> adj[MAX];

int sz[MAX];
bool kill[MAX];

void dfs_sz(int curr, int par)
{
    sz[curr]=1;
    for(pair<int,long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        dfs_sz(nxt.first,curr);
        sz[curr]+=sz[nxt.first];
    }
}

int get_centroid(int curr, int par, int N)
{
    for(pair<int,long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        if(sz[nxt.first]*2>N) return get_centroid(nxt.first,curr,N);
    }
    return curr;
}

long long mn[MAX];
vector<pair<int,long long>> anc[MAX];

void dfs(int curr, int par, int cen, long long dep)
{
    anc[curr].push_back({cen,dep});
    for(pair<int,long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        dfs(nxt.first,curr,cen,dep+nxt.second);
    }
}

void cd(int curr)
{
    dfs_sz(curr,-1);
    curr=get_centroid(curr,-1,sz[curr]);

    dfs(curr,-1,curr,0);

    kill[curr]=1;
    for(pair<int,long long> nxt: adj[curr])
    {
        if(kill[nxt.first]) continue;
        cd(nxt.first);
    }
}

void Init(int N, int A[], int B[], int D[])
{
    n=N;
    for(int i=0;i<N-1;i++)
    {
        int u=A[i],v=B[i],w=D[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    cd(0);
    for(int i=0;i<n;i++) mn[i]=INF;
}

void change(int curr, bool add)
{
    for(pair<int,long long> P: anc[curr])
    {
        int cen=P.first;
        long long w=P.second;
        if(add) mn[cen]=min(mn[cen],w);
        else mn[cen]=INF;
    }
}

long long query(int curr)
{
    long long ans=INF;
    for(pair<int, long long> P: anc[curr])
    {
        int cen=P.first;
        long long w=P.second;
        ans=min(ans,mn[cen]+w);
    }

    return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
    for(int i=0;i<S;i++) change(X[i],1);
    long long ans=INF;
    for(int i=0;i<T;i++) ans=min(ans,query(Y[i]));
    for(int i=0;i<S;i++) change(X[i],0);

    return ans;
}

/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
3 2
0 1 3
4 6
*/

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