Submission #111633

#	Time	Username	Problem	Language	Result	Execution time	Memory
111633		discoverMeMe	Factories (JOI14_factories)	C++14	0 / 100	29 ms	12544 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>>4;
bool blc[N];
vector<pair<int,int>> gr[N];

int lca(int x,int y)
{
	if(lvl[x]>lvl[y])
        swap(x,y);
	int dif=lvl[y]-lvl[x];
	fori(0,19)
        if(dif&(1<<i))
            y=par[y][i];
	if(x==y)
        return x;
	ford(i,19,0)
		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])
        {
            cnt++; st[i.first]=cnt; lvl[cnt]=lvl[st[x]]+1; len[cnt]=len[st[x]]+i.second; par[cnt][0]=st[x];
            forj(0,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;
}
/*
int aa[N],bb[N],cc[N],dd[N],ee[N];

int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    freopen("01-01.txt", "r", stdin);
    int q;
    cin>>n>>q;
    fori(0,n-1)
    {
        cin>>aa[i]>>bb[i]>>cc[i];
    }
    Init(n,aa,bb,cc);
    forj(0,q)
    {
        cin>>a>>b;
        fori(0,a)
            cin>>dd[i];
        fori(0,b)
            cin>>ee[i];
        cout<<Query(a,dd,b,ee)<<"\n";
    }
    //cout<<cnt<<endl;
    return 0;
}/**/

Compilation message (stderr)

factories.cpp:124:2: warning: "/*" within comment [-Wcomment]
 }/**/

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