제출 #1270506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270506		nerrrmin	공장들 (JOI14_factories)	C++20	0 / 100	8101 ms	268836 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const long long maxn = 5e5 + 10;

vector < pair < long long, long long > > g[maxn];

long long n, sub[maxn], blocked[maxn];
long long all, half;
void calc(long long beg, long long from)
{
    sub[beg] = 1;
    for (auto &[nb, dist]: g[beg])
    {
        if(nb == from)continue;
        if(blocked[nb])continue;
        sub[beg] += sub[nb];
    }
}
long long find_centroid(long long beg, long long from)
{
    for (auto [nb, cost]: g[beg])
    {
        if(nb == from || blocked[nb])continue;
        if(sub[nb] > half)return find_centroid(nb, beg);
    }
    return beg;
}
long long root, par[maxn];
long long decompose(long long v, long long from)
{
    calc(v, -1);
    all = sub[v];

    half = all/2;
    long long nc = find_centroid(v, -1);
    par[nc] = from;
    blocked[nc] = 1;
    for (auto &[nb, w]: g[nc])
    {
        if(blocked[nb])continue;
        int t = decompose(nb, nc);
    }
    return nc;
}
long long dep[maxn], p[maxn], pw[maxn];
long long a[maxn * 3], da[maxn * 3], tmr, label[maxn];
long long lg[maxn * 3], st[maxn * 3][20], dp[maxn * 3];
void dfs2(long long beg, long long from, long long d, long long up)
{

    dep[beg] = d;
    tmr ++;

    a[tmr] = beg;
    da[tmr] = d;
    label[beg] = tmr;

    dp[beg] = up;
    for (auto &[nb, cost]: g[beg])
    {
        if(nb == from)continue;
        pw[nb] = cost;
        p[nb] = beg;
        dfs2(nb, beg, d+1, up + cost);
        tmr ++;
        a[tmr] = beg;
        da[tmr] = d;
    }
}
long long lca(long long from, long long to)
{
    long long l = label[from], r = label[to];
    if(l > r)swap(l, r);
    long long sz = r - l + 1;
    long long lgche= lg[sz];
    long long fh = st[l][lgche];
    long long sh = st[r-(1 << lgche) + 1][lgche];
    if(da[fh] < da[sh])return a[fh];
    else return a[sh];
}
long long dist(long long u, long long v)
{
    long long anc = lca(u, v);

    return dp[u] + dp[v] - 2 * dp[anc];
}
long long best[maxn]; /// fix to ll
void Init(int N, int A[], int B[], int D[])
{
     n = N;
     for (long long i = 0; i < n-1; ++ i)
     {
         long long from = A[i], to = B[i], w = D[i];
         from ++;
         to ++;
         g[from].pb({to, w});
         g[to].pb({from, w});
     }

     root = decompose(1, -1);

     for (long long i = 0; i <= n; ++ i)
        best[i] = 1e17;
    dfs2(1, 0, 0, 0);

    long long step = 0, val = 1;
    for (long long i = 0; i <= tmr; ++ i)
    {
        if(val * 2<= i)
        {
            step ++;
            val *= 2;
        }
        lg[i] = step;
    }

    for (long long i = 1; i <= tmr; ++ i)
        st[i][0] = i;
    for (long long bit = 1; bit < 20; ++ bit)
    {
        for (long long i = 1; i + (1 << bit) - 1 <= tmr; ++ i)
        {
            long long fh = st[i][bit-1];
            long long sh = st[i + (1 << (bit - 1))][bit-1];
            if(da[fh] < da[sh])st[i][bit] = fh;
            else st[i][bit] = sh;
        }
    }

}

long long Query(int S, int X[], int T,  int Y[])
{
    long long s, t;
    s = S;
    t = T;
    /// update
    for (long long i = 0; i < s; ++ i)
    {
        X[i] ++;
        long long ver = X[i];
        while(ver != par[root])
        {
            best[ver] = min(best[ver], dist(ver, X[i]));
            ver = par[ver];
        }
    }
    long long ans = 1e17;
    for (long long i = 0; i < t; ++ i)
    {
        Y[i] ++;
        long long ver = Y[i];
        int cnt = 0;
        while(ver != par[root])
        {
            cnt ++;
            assert(cnt < n);
            ans = min(ans, best[ver] + dist(ver, Y[i]));
            ver = par[ver];
        }
    }
    /// kak shte go mahna posle
    for (long long i = 0; i < s; ++ i)
    {
        long long ver = X[i];
        while(ver != par[root])
        {
            best[ver] = 1e17;
            ver = par[ver];
        }
    }

  return ans;
}

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