Submission #156798

#	Time	Username	Problem	Language	Result	Execution time	Memory
156798		Alexa2001	Factories (JOI14_factories)	C++17	0 / 100	140 ms	48120 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;


void dfs0(int node, int dad = 0)
{
    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 = 0)
{
    int worst = n - 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 = 0)
{
    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=1; i<n; ++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]);
    }

    build(1);
}

ll Query(int S, int X[], int T, int Y[])
{
    map<int, ll> mp1, mp2;
    int i, j;

    for(i=0; i<S; ++i)
    {
        int node = X[i];
        for(j=0; j<root[node].size(); ++j)
            mp1[root[node][j]] = min(mp1[root[node][j]], h[node][j] - lim);
    }

    for(i=0; i<T; ++i)
    {
        int node = Y[i];
        for(j=0; j<root[node].size(); ++j)
            mp2[root[node][j]] = min(mp2[root[node][j]], h[node][j] - lim);
    }

    ll ans = lim;
    for(auto it : mp1)
        ans = min(ans, 2*lim + it.second + mp2[it.first]);

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:50: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:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<root[node].size(); ++j)
                  ~^~~~~~~~~~~~~~~~~~

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