Submission #51737

#	Time	Username	Problem	Language	Result	Execution time	Memory
51737		SpaimaCarpatilor	Factories (JOI14_factories)	C++17	100 / 100	4351 ms	180580 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

using namespace std;

int nr, rmq[20][1000009], lg[1000009], lev[500009], firstPos[500009], lastPos[500009], color[500009], ap[500009];
long long depth[500009], ans;
const long long INF = 1LL << 59;
vector < pair < int, int > > v[500009];

void dfs (int nod, int tata)
{
    rmq[0][++nr] = nod, firstPos[nod] = nr;
    for (auto it : v[nod])
        if (it.first != tata)
            depth[it.first] = depth[nod] + it.second,
            lev[it.first] = lev[nod] + 1, dfs (it.first, nod),
            rmq[0][++nr] = nod;
    lastPos[nod] = nr;
}

int getHigher (int x, int y)
{
    if (lev[x] > lev[y]) return y;
    return x;
}

int getLCA (int x, int y)
{
    x = firstPos[x], y = firstPos[y];
    if (x > y) swap (x, y);
    int p = lg[y - x + 1];
    return getHigher (rmq[p][x], rmq[p][y - (1 << p) + 1]);
}

bool cmp (int x, int y)
{
    return (firstPos[x] < firstPos[y]);
}

void Init (int N, int A[], int B[], int D[])
{
    for (int i=0; i<N - 1; i++)
    {
        A[i] ++, B[i] ++;
        v[A[i]].push_back ({B[i], D[i]});
        v[B[i]].push_back ({A[i], D[i]});
    }
    dfs (1, -1);
    for (int i=2; i<=nr; i++)
    {
        lg[i] = lg[i - 1];
        if ((2 << lg[i]) <= i)
            lg[i] ++;
    }
    for (int i=1; i<=lg[nr]; i++)
        for (int j=1; j + (1 << i) - 1<=nr; j++)
            rmq[i][j] = getHigher (rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
}

bool isAncestor (int up, int down)
{
    return (firstPos[up] <= firstPos[down] && lastPos[down] <= lastPos[up]);
}

vector < int > sons[500009];
pair < long long, long long > solve (int nod)
{
    pair < long long, long long > curr = {INF, INF};
    if (color[nod] == 1) curr.first = depth[nod];
    else
    if (color[nod] == 2) curr.second = depth[nod];
    for (auto it : sons[nod])
    {
        auto currIt = solve (it);
        if (currIt.first < curr.first) curr.first = currIt.first;
        if (currIt.second < curr.second) curr.second = currIt.second;
    }
    if (curr.first + curr.second - 2LL * depth[nod] < ans)
        ans = curr.first + curr.second - 2LL * depth[nod];
    return curr;
}

int stk[500009], h[500009];
long long Query (int S, int X[], int T, int Y[])
{
    nr = 0, ans = INF;
    for (int i=0; i<S; i++)
        X[i] ++, h[++nr] = X[i], color[X[i]] = 1, ap[X[i]] = 1;
    for (int i=0; i<T; i++)
        Y[i] ++, h[++nr] = Y[i], color[Y[i]] = 2, ap[Y[i]] = 1;
    sort (h + 1, h + nr + 1, cmp);
    for (int i=nr - 1; i>=1; i--)
    {
        int curr = getLCA (h[i], h[i + 1]);
        if (ap[curr] == 0)
            ap[curr] = 2, h[++nr] = curr;
    }
    sort (h + 1, h + nr + 1, cmp);
    int l = 0, root = 0;
    for (int i=1; i<=nr; i++)
    {
        while (l > 0 && isAncestor (stk[l], h[i]) == 0) l --;
        if (l == 0) root = h[i];
        else sons[stk[l]].push_back (h[i]);
        stk[++l] = h[i];
    }
    solve (root);
    for (int i=1; i<=nr; i++)
        ap[h[i]] = 0, color[h[i]] = 0,
        sons[h[i]].clear ();
    return ans;
}

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