Submission #656615

#	Time	Username	Problem	Language	Result	Execution time	Memory
656615		Tuanlinh123	Factories (JOI14_factories)	C++17	0 / 100	30 ms	12500 KiB

factories

// #define _GLIBCXX_DEBUG
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

ll n, k;
vector <pll> euler;
vector <pll> a[500005];
ll dist[500005], dis[500005], dep[500005], t[500005], Time;
priority_queue <pll, vector <pll>, greater<pll>> q;

void dfs(ll u, ll pa)
{
    t[u]=++Time;
    euler.pb({dep[u], u});
    for (pll ed:a[u])
    {
        ll v=ed.fi, w=ed.se;
        if (v==pa)
            continue;
        dep[v]=dep[u]+1;
        dist[v]=dist[u]+w;
        dfs(v, u);
        euler.pb({dep[u], u});
    }
}

struct Sparse
{
    ll n;
    vector <ll> lg;
    vector <vector <pll>> sp;

    void init(ll n)
    {
        this->n=n;
        lg.assign(n+5, 0);
        for (ll i=2; i<=n; i++)
            lg[i]=lg[i/2]+1;
        sp.resize(lg[n]+5);
        for (ll i=0; i<=lg[n]; i++)
            sp[i].assign(n+5, {0, 0});
        for (ll i=1; i<=n; i++)
            sp[0][i]=euler[i-1];
        for (ll i=1; i<=lg[n]; i++)
            for (ll j=1; j+(1<<i)<=n+1; j++)
                sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
    }

    ll LCA(ll u, ll v)
    {
        u=t[u], v=t[v];
        if (u>v) swap(u, v);
        ll j=lg[v-u+1];
        return min(sp[j][u], sp[j][v-(1<<j)+1]).se;
    }
    
    ll distance(ll u, ll v)
    {
        ll p=LCA(u, v);
        return dis[u]+dis[v]-dis[p]*2;
    }
} b;

void Init(int N, int A[], int B[], int C[]) 
{
    n=N; k=floor(sqrt(n));
    for (ll i=0; i<n-1; i++)
        a[A[i]].pb({B[i], C[i]}), a[B[i]].pb({A[i], C[i]});
    dfs(0, 0);
    b.init(euler.size());
}

ll Query(int S, int X[], int T, int Y[])
{
    if (S>=k || T>=k)
    {
        for (ll i=0; i<n; i++)
            dis[i]=-1;
        for (ll i=0; i<S; i++)
        {
            dis[X[i]]=0;
            q.push({0, X[i]});
        }
        while(!q.empty())
        {
            pll t=q.top(); q.pop();
            ll disu=t.fi, u=t.se;
            if (dis[u]!=disu)
                continue;
            // cout << u << " " << dis[u] << "\n";
            for (pll ed:a[u])
            {
                ll v=ed.fi, w=ed.se;
                // cout << v << " " << w << " ";
                if (dis[v]==-1 || dis[v]>disu+w)
                {
                    dis[v]=disu+w;
                    q.push({dis[v], v});
                }
            }
            // cout << "\n";
        }
        ll ans=1e18;
        for (ll i=0; i<T; i++)
            ans=min(ans, dis[Y[i]]);
        return ans;
    }
    else
    {
        ll ans=1e18;
        for (ll i=0; i<S; i++)
            for (ll j=0; j<T; j++)
                ans=min(ans, b.distance(X[i], Y[j]));
        return ans;
    }
}

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