oj.uz

Submission #656643

# Submission time Handle Problem Language Result Execution time Memory
656643 2022-11-08T02:53:17 Z Tuanlinh123 Factories (JOI14_factories) C++17
0 / 100
 26 ms 12500 KB 
// #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], t[500005], Time;
priority_queue <pll, vector <pll>, greater<pll>> q;

void dfs(ll u, ll pa)
{
    t[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});
    }
}

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=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 u, ll v)
    {
        u=t[u], v=t[v];
        if (u>v) swap(u, v);
        ll j=lg[v-u+1];
        ll ans=min(sp[j][u], sp[j][v-(1<<j)+1]).se;
        return ans;
    }
    
    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*20));
    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(1, 1);
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12500 KB Output isn't correct
2 Halted 0 ms 0 KB -