Submission #156804

#	Time	Username	Problem	Language	Result	Execution time	Memory
156804		Alexa2001	Factories (JOI14_factories)	C++17	15 / 100	8026 ms	338908 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];


void dfs0(int node, int dad = -1)
{
    w[node] = 1;
    for(auto it : v[node])
        if(!used[it] && it!=dad)
        {
            dfs0(it, node);
            w[node] += w[it];
        }
}

Pair centroid(int node, int dad = -1)
{
    int worst = All - w[node];
    Pair best = {n, n};

    for(auto it : v[node])
        if(!used[it] && it != dad)
        {
            best = min(best, centroid(it, node));
            worst = max(worst, w[it]);
        }
    best = min(best, {worst, node});
    return best;
}

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)
{
    dfs0(node);
    All = w[node];
    node = centroid(node).second;

    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:51: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:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:132: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: 0 / 18
• Subtask 3: 0 / 67