Submission #1176417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176417		vnedu	Factories (JOI14_factories)	C++20	100 / 100	2460 ms	148320 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 5e5 + 55;
const ll inf = 1e17;
int n,dep[N],up[N][20],tg=0,st[N],en[N];
ll dis[N];
vector<ii> adj[N];
void dfs(int u, int pa)
{
    st[u]=++tg;
    up[u][0]=pa;
    for (int j=1; j<20; ++j) if ((1<<j)<dep[u]) up[u][j]=up[up[u][j-1]][j-1];
    for (ii p : adj[u])
    {
        int v=p.fi,w=p.se;
        if (v==pa) continue;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
    en[u]=++tg;
}
int findLca(int u, int v)
{
    if (dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    for (int j=0; j<20; ++j) if ((k>>j)&1) u=up[u][j];
    if (u==v) return u;
    for (int j=19; j>=0; --j) if ((1<<j)<dep[u])
    {
        if (up[u][j]!=up[v][j])
        {
            u=up[u][j];
            v=up[v][j];
        }
    }
    return up[u][0];
}
bool inside(int pa, int u)
{
    return (st[pa]<=st[u] && st[u]<=en[pa]);
}

void Init(int _n, int A[], int B[], int D[]) {
    n=_n;
    for (int i=0; i<n-1; ++i)
    {
        int u=A[i],v=B[i],w=D[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dep[0]=1;
    dis[0]=0;
    dfs(0,-1);
}
bool dfsTimer(int u, int v)
{
    return st[u]<st[v];
}
int a[N*2],k,nroot,id[N];
vector<pair<int,ll>> nadj[N];
stack<int> stk;
pair<pair<ll,int>,pair<ll,int>> dp[N];
void update(int u, int v, ll w)
{
    pair<ll,int> cm;
    if (dp[v].fi.se==u) cm=dp[v].se;
    else cm=dp[v].fi;
    cm.fi+=w;
    if (id[v]==1) minimize(cm,make_pair(w,v));
    if (cm<dp[u].fi) dp[u].se=dp[u].fi,dp[u].fi=cm;
    else if (cm<dp[u].se) dp[u].se=cm;
}
void notreroot(int u, int pa)
{
    dp[u]=make_pair(make_pair(inf,-1),make_pair(inf,-1));
    for (pair<int,ll> p : nadj[u])
    {
        int v=p.fi; ll w=p.se;
        if (v==pa) continue;
        notreroot(v,u);
        update(u,v,w);
    }
//    cerr<<u<<' '<<dp[u].fi.fi<<' '<<dp[u].fi.se<<' '<<dp[u].se.fi<<' '<<dp[u].se.se<<'\n';
}
ll reroot(int u, int pa)
{
    ll ans=inf;
//    cerr<<"DSDASDIASHDIU "<<u<<' '<<id[u]<<'\n';
    if (id[u]==-1) minimize(ans,dp[u].fi.fi);
    for (pair<int,ll> p : nadj[u])
    {
        int v=p.fi; ll w=p.se;
        if (v==pa) continue;
        pair<pair<ll,int>,pair<ll,int>> old=dp[v];
        dp[v]=make_pair(make_pair(inf,-1),make_pair(inf,-1));
        for (pair<int,ll> gaugau : nadj[v])
        {
            update(v,gaugau.fi,gaugau.se);
        }
        minimize(ans,reroot(v,u));
        dp[v]=old;
    }
    return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
    k=0;
    for (int j=0; j<S; ++j) a[++k]=X[j],id[X[j]]=-1;
    for (int j=0; j<T; ++j) a[++k]=Y[j],id[Y[j]]=1;
    sort(a+1,a+1+k,dfsTimer);
    for (int i=2; i<=k; ++i) a[i+k-1]=findLca(a[i],a[i-1]);
    k=2*k-1;
    sort(a+1,a+1+k,dfsTimer);
    k=unique(a+1,a+1+k)-a-1;
//    cerr<<k<<'\n';
//    for (int i=1; i<=k; ++i) cerr<<a[i]<<' ';
//    cerr<<'\n';
    nroot=a[1];
//    cerr<<nroot<<'\n';
    while (!stk.empty()) stk.pop();
    stk.push(nroot);
    for (int i=2; i<=k; ++i)
    {
        int u=a[i];
        while (!inside(stk.top(),u)) stk.pop();
        int v=stk.top();
        ll w=dis[u]-dis[v];
//        cerr<<u<<' '<<v<<' '<<w<<'\n';
        nadj[u].pb({v,w});
        nadj[v].pb({u,w});
        stk.push(u);
    }
//    for (int i=0; i<n; ++i) cerr<<id[i]<<' ';
//    cerr<<'\n';
    notreroot(nroot,-1);

    ll ans=reroot(nroot,-1);

    // reset
    for (int j=0; j<S; ++j) id[X[j]]=0;
    for (int j=0; j<T; ++j) id[Y[j]]=0;
    for (int i=1; i<=k; ++i) vector<pair<int,ll>>().swap(nadj[a[i]]);

    return ans;
}

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