제출 #111643

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

factories

#include <bits/stdc++.h>
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int N=500001;
int n,cnt,st[N],ed[N],par[N][20],lvl[N],a,b,c,cand[N*2],ext[N],pcnt;
long long U[N],V[N],xx,len[N],MAX=LLONG_MAX>>2;
bool blc[N];
vector<pair<int,int>> gr[N];

int lca(int x,int y)
{
	if (lvl[x]>lvl[y])
        swap(x,y);
	int up=lvl[y]-lvl[x];
	ford(i,19,0)
        if(up&(1<<i))
            y=par[y][i];
	if (x==y)
        return x;
	for (int i=19;i>=0;i--)
		if (par[x][i]!=par[y][i])
		{
			x=par[x][i];
			y=par[y][i];
		}
	return par[x][0];
}
void dfs(int x)
{
	blc[x]=true;
	for (auto i:gr[x])
        if(!blc[i.first])
        {
            st[i.first]=++cnt; lvl[cnt]=lvl[st[x]]+1; len[cnt]=len[st[x]]+i.second; par[cnt][0]=st[x];
            forj(1,20)
                par[cnt][j]=par[par[cnt][j-1]][j-1];
            dfs(i.first);
        }
	ed[st[x]]=cnt;
}
void Init(int N,int A[],int B[],int D[])
{
	fori(0,N-1)
	{
		gr[A[i]].push_back({B[i],D[i]});
		gr[B[i]].push_back({A[i],D[i]});
	}
	st[0]=cnt=1;
	dfs(0);
}
int pdfs(int x)
{
	U[x]=V[x]=MAX;
	if(ext[cand[x]]==1)
        U[x]=0;
	if(ext[cand[x]]==2)
        V[x]=0;
	int e=x+1;
	while(e<pcnt&&cand[e]<=ed[cand[x]])
	{
		a=pdfs(e);
		U[x]=min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
		V[x]=min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
		e=a;
	}
	xx=min(xx,U[x]+V[x]);
	ext[cand[x]]=0;
	return e;
}

long long Query(int S,int X[],int T,int Y[])
{
	pcnt=0;
	for(int i=0;i<S;i++)
    {
        cand[pcnt++]=st[X[i]];
        ext[st[X[i]]]=1;
    }
	for(int i=0;i<T;i++)
    {
        cand[pcnt++]=st[Y[i]];
        ext[st[Y[i]]]=2;
    }
	sort(cand,cand+pcnt);
	for(int i=1;i<S+T;i++)
        cand[pcnt++]=lca(cand[i-1],cand[i]);
	sort(cand,cand+pcnt);
	pcnt=unique(cand,cand+pcnt)-cand;
	xx=MAX;
	pdfs(0);
	return xx;
}

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