제출 #310910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310910		vipghn2003	공장들 (JOI14_factories)	C++14	100 / 100	4406 ms	150260 KiB

factories

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=5e5+5;
int n,m,p[N][21],level[N],sz[N],l[N],r[N],type[N],node[N*2];
long long mn[N][2],dep[N],res;
vector<pii>adj[N];
vector<int>g[N];

int cnt=0;
void dfs(int u)
{
    for(int i=1;i<=20;i++) p[u][i]=p[p[u][i-1]][i-1];
    cnt++;
    l[u]=cnt;
    for(auto&to:adj[u])
    {
        int v=to.fi;
        int w=to.se;
        if(v==p[u][0]) continue;
        p[v][0]=u;
        dep[v]=dep[u]+w;
        level[v]=level[u]+1;
        dfs(v);
    }
    r[u]=cnt;
}

int lca(int x,int y)
{
    if(level[x]>level[y]) swap(x,y);
    int diff=level[y]-level[x];
    for(int k=20;k>=0;k--) if(diff>>k&1) y=p[y][k];
    if (x==y) return x;
    for(int k=20;k>=0;k--)
    {
        if (p[x][k]!=p[y][k])
        {
            x=p[x][k];
            y=p[y][k];
        }
    }
    return p[x][0];
}

bool isParent(int p,int u)
{
    return (l[p]<=l[u]&&l[u]<=r[p]);
}

bool lf(const int &x,const int &y)
{
    return l[x]<l[y];
}

void Init(int N,int A[],int B[],int D[])
{
    n=N;
    cnt=0;
    for(int i=1;i<=n;i++) type[i]=-1;
    for(int i=0;i<n-1;i++)
    {
        int u=A[i];
        int v=B[i];
        int w=D[i];
        u++,v++;
        adj[u].push_back(mp(v,w));
        adj[v].push_back(mp(u,w));
    }
    dfs(1);
}

void go(int u,int par=-1)
{
    if(type[u]==0) mn[u][0]=dep[u];
    if(type[u]==1) mn[u][1]=dep[u];
    for(auto&v:g[u])
    {
        if(v==par) continue;
        go(v,u);
        res=min(res,mn[u][0]+mn[v][1]-2*dep[u]);
        res=min(res,mn[v][0]+mn[u][1]-2*dep[u]);
        mn[u][0]=min(mn[u][0],mn[v][0]);
        mn[u][1]=min(mn[u][1],mn[v][1]);
    }
}

long long Query(int S,int X[],int T,int Y[])
{
    int total_num=0;
    for(int i=0;i<S;i++)
    {
        X[i]++;
        type[X[i]]=0;
        total_num++;
        node[total_num]=X[i];
    }
    for(int i=0;i<T;i++)
    {
        Y[i]++;
        type[Y[i]]=1;
        total_num++;
        node[total_num]=Y[i];
    }
    sort(node+1,node+total_num+1,lf);
    total_num=unique(node+1,node+total_num+1)-node-1;
    int now=total_num;
    for(int i=1;i<now;i++)
    {
        total_num++;
        node[total_num]=lca(node[i],node[i+1]);
    }
    sort(node+1,node+total_num+1,lf);
    total_num=unique(node+1,node+total_num+1)-node-1;
    for(int i=1;i<=total_num;i++)
    {
        g[node[i]].clear();
        mn[node[i]][0]=1e18;
        mn[node[i]][1]=1e18;
    }
    stack<int>st;
    st.push(node[1]);
    for(int i=2;i<=total_num;i++)
    {
        while(!st.empty()&&!isParent(st.top(),node[i])) st.pop();
        if(!st.empty())
        {
            int par=st.top();
            g[par].push_back(node[i]);
            g[node[i]].push_back(par);
        }
        st.push(node[i]);
    }
    res=1e18;
    go(node[1]);
    for(int i=0;i<S;i++) type[X[i]]=-1;
    for(int i=0;i<T;i++) type[Y[i]]=-1;
    return res;
}

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