Submission #1270516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270516		nerrrmin	Factories (JOI14_factories)	C++20	0 / 100	458 ms	165184 KiB

factories

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

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

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

    half = all/2;
    int 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;
}
int dep[maxn], p[maxn], pw[maxn];
int a[maxn * 3], da[maxn * 3], tmr, label[maxn];
int lg[maxn * 3], st[maxn * 3][23];
long long dp[maxn * 3];
void dfs2(int beg, int from, int d, int 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;
    }
}
int lca(int from, int to)
{
    int l = label[from], r = label[to];
    if(l > r)swap(l, r);
    int sz = r - l + 1;
    int lgche= lg[sz];
    int fh = st[l][lgche];
    int sh = st[r-(1 << lgche) + 1][lgche];
    if(da[fh] < da[sh])return a[fh];
    else return a[sh];
}
long long dist(int u, int v)
{
    int anc = lca(u, v);

    return 1LL * 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 (int i = 0; i < n-1; ++ i)
     {
         int 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 (int i = 0; i <= n; ++ i)
        best[i] = 1e17;
    dfs2(1, 0, 0, 0);

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

    for (int i = 1; i <= tmr; ++ i)
        st[i][0] = i;
    for (int bit = 1; bit < 23; ++ bit)
    {
        for (int i = 1; i + (1 << bit) - 1 <= tmr; ++ i)
        {
            int fh = st[i][bit-1];
            int 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[])
{
    int s, t;
    s = S;
    t = T;
    /// update
    for (int i = 0; i < s; ++ i)
    {
        X[i] ++;
        int ver = X[i];
        while(ver != par[root])
        {
            best[ver] = min(best[ver], dist(ver, X[i]));
            ver = par[ver];
        }
    }
    long long ans = 1e17;
    for (int i = 0; i < t; ++ i)
    {
        Y[i] ++;
        int ver = Y[i];
        int cnt = 0;
        while(ver != par[root])
        {
            cnt ++;
            assert(cnt < 30);
            ans = min(ans, best[ver] + dist(ver, Y[i]));
            ver = par[ver];
        }
    }
    /// kak shte go mahna posle
    for (int i = 0; i < s; ++ i)
    {
        int 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