Submission #1016156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016156		raphaelp	Factories (JOI14_factories)	C++14	100 / 100	3814 ms	377428 KiB

factories

#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> centroids;
vector<long long> best;
void updateSub(long long x, long long p, vector<vector<pair<long long, long long>>> &AR, vector<long long> &subtree, vector<long long> &done)
{
    subtree[x] = 1;
    for (long long i = 0; i < AR[x].size(); i++)
    {
        if (done[AR[x][i].first])
            continue;
        if (AR[x][i].first == p)
            continue;
        updateSub(AR[x][i].first, x, AR, subtree, done);
        subtree[x] += subtree[AR[x][i].first];
    }
}
void addCentre(long long x, long long p, long long centre, vector<vector<pair<long long, long long>>> &AR, vector<long long> &done, long long dist)
{
    centroids[x].push_back({centre, dist});
    for (long long i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p)
            continue;
        if (done[AR[x][i].first])
            continue;
        addCentre(AR[x][i].first, x, centre, AR, done, dist + AR[x][i].second);
    }
}
void decompose(long long x, vector<vector<pair<long long, long long>>> &AR, vector<long long> &done, vector<long long> &subtree)
{
    updateSub(x, x, AR, subtree, done);
    long long centre = x, last = x;
    while (true)
    {
        long long next = -1;
        for (long long i = 0; i < AR[centre].size(); i++)
        {
            if (done[AR[centre][i].first])
                continue;
            if (AR[centre][i].first == last)
                continue;
            if (subtree[AR[centre][i].first] > subtree[x] / 2)
                next = AR[centre][i].first;
        }
        if (next == -1)
            break;
        last = centre;
        centre = next;
    }
    done[centre] = 1;
    addCentre(centre, centre, centre, AR, done, 0);
    for (int i = 0; i < AR[centre].size(); i++)
    {
        if (done[AR[centre][i].first])
            continue;
        decompose(AR[centre][i].first, AR, done, subtree);
    }
}
void Init(int N, int A[], int B[], int D[])
{
    vector<vector<pair<long long, long long>>> AR(N);
    vector<long long> done(N);
    for (long long i = 0; i < N - 1; i++)
    {
        AR[A[i]].push_back({B[i], D[i]});
        AR[B[i]].push_back({A[i], D[i]});
    }
    centroids.assign(N, {});
    best.assign(N, 123456789123456789);
    vector<long long> subtree(N);
    decompose(0, AR, done, subtree);
}
long long Query(int S, int X[], int T, int Y[])
{
    for (int i = 0; i < S; i++)
    {
        for (int j = 0; j < centroids[X[i]].size(); j++)
        {
            best[centroids[X[i]][j].first] = min(best[centroids[X[i]][j].first], centroids[X[i]][j].second);
        }
    }
    long long ans = 123456789123456789;
    for (int i = 0; i < T; i++)
    {
        for (int j = 0; j < centroids[Y[i]].size(); j++)
        {
            ans = min(ans, best[centroids[Y[i]][j].first] + centroids[Y[i]][j].second);
        }
    }
    for (int i = 0; i < S; i++)
    {
        for (int j = 0; j < centroids[X[i]].size(); j++)
        {
            best[centroids[X[i]][j].first] = 123456789123456789;
        }
    }
    return ans;
}
/*int main()
{
    int N, Q;
    cin >> N >> Q;
    int A[N - 1], B[N - 1], D[N - 1];
    for (int i = 0; i < N - 1; i++)
    {
        cin >> A[i] >> B[i] >> D[i];
    }
    Init(N, A, B, D);
    for (int i = 0; i < Q; i++)
    {
        int S, T;
        cin >> S >> T;
        int X[S], Y[T];
        for (int j = 0; j < S; j++)
        {
            cin >> X[j];
        }
        for (int j = 0; j < T; j++)
        {
            cin >> Y[j];
        }
        cout << Query(S, X, T, Y) << endl;
    }
}*/

Compilation message (stderr)

factories.cpp: In function 'void updateSub(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&)':
factories.cpp:8:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (long long i = 0; i < AR[x].size(); i++)
      |                           ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void addCentre(long long int, long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, long long int)':
factories.cpp:21:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (long long i = 0; i < AR[x].size(); i++)
      |                           ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void decompose(long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&)':
factories.cpp:37:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (long long i = 0; i < AR[centre].size(); i++)
      |                               ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < AR[centre].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int j = 0; j < centroids[X[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int j = 0; j < centroids[Y[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int j = 0; j < centroids[X[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~

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