Submission #111639

#	Time	Username	Problem	Language	Result	Execution time	Memory
111639		discoverMeMe	Factories (JOI14_factories)	C++14	100 / 100	3531 ms	108684 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] = 1;

	for (int i=0;i<gr[x].size();i++){
		pair<int, int> p = gr[x][i];
		if (blc[p.first]) continue;
		st[p.first] = ++cnt;
		lvl[cnt] = lvl[st[x]] + 1;
		len[cnt] = len[st[x]] + p.second;
		par[cnt][0] = st[x];
		for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
		dfs(p.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:127:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
factories.cpp: In function 'void dfs(int)':
factories.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<gr[x].size();i++){
               ~^~~~~~~~~~~~~

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