Submission #656740

#	Time	Username	Problem	Language	Result	Execution time	Memory
656740		Tuanlinh123	Factories (JOI14_factories)	C++17	100 / 100	6007 ms	450020 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, Time;
ll tin[500005], tout[500005], dist[500005], dis[500005];
vector <pll> euler;
vector <pll> a[500005];
priority_queue <pll, vector <pll>, greater<pll>> q;

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

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

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

    ll LCA(ll l, ll r)
    {
        l=tin[l], r=tin[r];
        if (l>r) swap(l, r);
        ll j=lg[r-l+1];
        return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
    }

    ll distance(ll u, ll v)
    {
        ll p=LCA(u, v);
        ll ans=dist[u]+dist[v]-dist[p]*2;
        return ans;
    }
} b;



void Init(int N, int A[], int B[], int C[]) 
{
    n=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());
}

bool cmp(ll a, ll b)
{
    return tin[a]<tin[b];
}

ll Query(int S, int X[], int T, int Y[])
{
    map <ll, ll> Map;
    vector <ll> ver;
    vector <vector <pll>> edge;
    for (ll i=0; i<S; i++)
        ver.pb(X[i]);
    for (ll i=0; i<T; i++)
        ver.pb(Y[i]);
    sort(ver.begin(), ver.end(), cmp);
    for (ll i=ver.size()-1; i>=1; i--)
        ver.pb(b.LCA(ver[i], ver[i-1]));
    sort(ver.begin(), ver.end(), cmp);
    ver.resize(unique(ver.begin(), ver.end())-ver.begin());
    edge.resize(ver.size());
    vector <ll> st;
    for (ll i=0; i<ver.size(); i++)
    {
        dis[i]=-1;
        Map[ver[i]]=i;
        if (i==0)
        {
            st.pb(i);
            continue;
        }
        while (tin[ver[st.back()]]>tin[ver[i]] || tout[ver[st.back()]]<tout[ver[i]])
            st.pop_back();
        edge[i].pb({st.back(), b.distance(ver[i], ver[st.back()])});
        edge[st.back()].pb({i, b.distance(ver[i], ver[st.back()])});
        st.pb(i);
    }
    for (ll i=0; i<S; i++)
        dis[Map[X[i]]]=0, q.push({0, Map[X[i]]});
    while (!q.empty())
    {
        ll u=q.top().se, disu=q.top().fi; q.pop();
        if (dis[u]!=disu)
            continue;
        for (pll ed:edge[u])
        {
            ll v=ed.fi, w=ed.se;
            if (dis[v]==-1 || dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({dis[v], v});
            }
        }
    }
    ll ans=1e18;
    for (ll i=0; i<T; i++)
        ans=min(ans, dis[Map[Y[i]]]);
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:106:19: 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]
  106 |     for (ll i=0; i<ver.size(); i++)
      |                  ~^~~~~~~~~~~

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