Submission #1238988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238988		denislav	Factories (JOI14_factories)	C++20	0 / 100	413 ms	589824 KiB

factories

# include <iostream>
# include <vector>
# include <set>
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];

int 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;
}

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);
}

multiset<long long> s[MAX];

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) s[cen].insert(w);
        else s[cen].erase(s[cen].find(w));
    }
}

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;
        if((int)s[cen].size()>0) ans=min(ans,w+*s[cen].begin());
    }

    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
*/

Compilation message (stderr)

factories.cpp: In function 'int dfs_sz(int, int)':
factories.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
   26 | }
      | ^

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