Submission #156805

#	Time	Username	Problem	Language	Result	Execution time	Memory
156805		Alexa2001	Factories (JOI14_factories)	C++17	100 / 100	7593 ms	338620 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;

const int Nmax = 5e5 + 5;
const ll lim = 1e17;

vector<ll> h[Nmax];
vector<int> root[Nmax];
vector<int> v[Nmax], c[Nmax];

int w[Nmax];
bool used[Nmax];
int n, All;
ll best[Nmax];
int up[Nmax], worst[Nmax];
vector<int> nodes;


void dfs0(int node, int dad = -1)
{
    w[node] = 1;
    nodes.push_back(node);

    for(auto it : v[node])
        if(!used[it] && it!=dad)
        {
            dfs0(it, node);
            worst[node] = max(worst[node], w[it]);
            w[node] += w[it];
        }
}

void dfs(int node, int dad = -1)
{
    int i;
    for(i=0; i<v[node].size(); ++i)
    {
        int son, cost;
        son = v[node][i], cost = c[node][i];

        if(used[son] || son == dad) continue;

        h[son].push_back(h[node].back() + cost);
        root[son].push_back(root[node].back());

        dfs(son, node);
    }
}

void build(int node)
{
    nodes.clear();
    dfs0(node);
    All = w[node];

    Pair centroid = {All, All};
    for(auto &it : nodes)
        centroid = min(centroid, { max(worst[it], All - w[it]), it });
    node = centroid.second;

    for(auto &it : nodes) worst[it] = 0;

    h[node].push_back(0);
    root[node].push_back(node);
    dfs(node);

    used[node] = 1;

    for(auto it : v[node])
        if(!used[it])
            build(it);
}

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    int i;

    for(i=0; i<n-1; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        c[A[i]].push_back(D[i]);
        c[B[i]].push_back(D[i]);
    }

    for(i=0; i<n; ++i) best[i] = lim;

    build(0);
}

static void min_to(ll &x, ll y)
{
    if(x > y) x = y;
}

ll Query(int S, int X[], int T, int Y[])
{
    int i, j;
    vector<pair<int,ll>> S1, S2;

    for(i=0; i<S; ++i)
    {
        int node = X[i];

        for(j=0; j<root[node].size(); ++j)
            min_to( best[root[node][j]], h[node][j] );
    }

    ll ans = lim;

    for(i=0; i<T; ++i)
    {
        int node = Y[i];

        for(j=0; j<root[node].size(); ++j)
            min_to(ans, best[root[node][j]] + h[node][j] );
    }

    for(i=0; i<S; ++i)
    {
        int node = X[i];

        for(j=0; j<root[node].size(); ++j)
            best[root[node][j]] = lim;
    }

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~

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