Submission #156803

#	Time	Username	Problem	Language	Result	Execution time	Memory
156803		Alexa2001	Factories (JOI14_factories)	C++17	15 / 100	8100 ms	345840 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 = -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]);
    }

    build(0);
}

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)
            S1.push_back({ root[node][j], h[node][j] });
    }

    for(i=0; i<T; ++i)
    {
        int node = Y[i];
        for(j=0; j<root[node].size(); ++j)
            S2.push_back({ root[node][j], h[node][j] });
    }

    sort(S1.begin(), S1.end());
    sort(S2.begin(), S2.end());

    ll ans = lim;

    j = 0;
    for(i=0; i<S1.size(); ++i)
    {
        while(j<S2.size() && S2[j].first < S1[i].first) ++j;

        if(j<S2.size() && S2[j].first == S1[i].first)
            ans = min(ans, S1[i].second + S2[j].second);
    }

    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)
                  ~^~~~~~~~~~~~~~~~~~
factories.cpp:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<S1.size(); ++i)
              ~^~~~~~~~~~
factories.cpp:124:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j<S2.size() && S2[j].first < S1[i].first) ++j;
               ~^~~~~~~~~~
factories.cpp:126:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(j<S2.size() && S2[j].first == S1[i].first)
            ~^~~~~~~~~~

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