Submission #364515

#	Time	Username	Problem	Language	Result	Execution time	Memory
364515		blue	Factories (JOI14_factories)	C++17	0 / 100	35 ms	32108 KiB

factories

#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
Assign DFS entry label to all the nodes of the tree.
For each query, replace the nodes with the corresponding DFS labels.
Sort the input sets.
*/
long long P[500001][20];
long long Pdist[500001][20];
vector<long long> edge[500001];
vector<long long> dist[500001];

long long curr_label = 0;
vector<long long> depth(500001, 0);
vector<long long> label(500001, -1);



void dfs_binary(long long u)
{
    for(long long i = 0; i < edge[u].size(); i++)
    {
        long long v = edge[u][i], d = dist[u][i];

        if(P[v][0] != -1) continue;
        P[v][0] = u;
        Pdist[v][0] = d;

        dfs_binary(v);
    }
}



void dfs_label(long long u)
{
    label[u] = curr_label;
    curr_label++;

    for(long long v: edge[u])
    {
        if(label[v] > -1) continue;
        depth[v] = depth[u] + 1;
        dfs_label(v);
    }
}



long long find_dist(long long u, long long v)
{
    long long res = 0;
    if(depth[u] < depth[v]) swap(u, v);


    for(long long bit = 19; bit >= 0; bit--)
    {
        if(depth[u] - (1 << bit) > depth[v])
        {
            res += Pdist[u][bit];
            u = P[u][bit];
        }
    }
    if(depth[u] > depth[v])
    {
        res += Pdist[u][0];
        u = P[u][0];
    }

    // cerr << u << ' ' << v << ' ' << res <<  '\n';


    for(long long bit = 19; bit >= 0; bit--)
    {
        if(P[u][bit] != P[v][bit])
        {
            // cerr << "bit = " << bit << '\n';
            res += Pdist[u][bit];
            u = P[u][bit];

            res += Pdist[v][bit];
            v = P[u][bit];
        }
    }
    if(u != v)
    {
        res += Pdist[u][0];
        res += Pdist[v][0];
    }
    // cerr << u << ' ' << v << ' ' << res <<  '\n';

    return res;
}



void Init(int N, int A[], int B[], int D[])
{

    for(long long i = 0; i < N-1; i++)
    {
        edge[A[i]].push_back(B[i]);
        dist[A[i]].push_back(D[i]);

        edge[B[i]].push_back(A[i]);
        dist[B[i]].push_back(D[i]);
    }

    for(long long i = 0; i < N; i++) P[i][0] = -1;

    P[0][0] = 0;
    dfs_binary(0);

    // for(long long i = 0; i < N; i++)
    // {
    //     cerr << P[i][0] << '-' << Pdist[i][0] << ' ';
    // }
    // cerr << '\n';

    for(long long p = 1; p < 20; p++)
    {
        for(long long i = 0; i < N; i++)
        {
            P[i][p] = P[ P[i][p-1] ][p-1];
            Pdist[i][p] = Pdist[i][p-1] + Pdist[ P[i][p-1] ][p-1];
            // cerr << P[i][p] << '-' << Pdist[i][p] << ' ';
        }
        // cerr << '\n';
    }

    depth[0] = 0;
    dfs_label(0);
    // for(long long i = 0; i < N; i++) cerr << label[i] << ' ';
    // cerr << '\n';
}

long long Query(int S, int X[], int T, int Y[])
{
    sort(X, X+S, [] (long long p, long long q)
    {
        return label[p] < label[q];
    });

    sort(Y, Y+T, [] (long long p, long long q)
    {
        return label[p] < label[q];
    });

    long long res = 1e9;
    long long x = 0, y = 0;

    for(x = 0; x < S; x++)
    {
        res = min(res, find_dist(X[x], Y[y]));
        // cerr << "comparing " << X[x] << ' ' << Y[y] << '\n';
        while(y+1 < T && find_dist(X[x], Y[y+1]) <= find_dist(X[x], Y[y]))
        {
            y++;
            // cerr << "comparing " << X[x] << ' ' << Y[y] << '\n';
            res = min(res, find_dist(X[x], Y[y]));
        }
    }

    return res;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs_binary(long long int)':
factories.cpp:25:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(long long i = 0; i < edge[u].size(); i++)
      |                          ~~^~~~~~~~~~~~~~~~

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