Submission #111637

#	Time	Username	Problem	Language	Result	Execution time	Memory
111637		discoverMeMe	Factories (JOI14_factories)	C++14	100 / 100	3728 ms	108796 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];
	for (int i=19;i>=0;i--) 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[])
{
	for (int i=0;i<N-1;i++){
		gr[A[i]].push_back(make_pair(B[i],D[i]));
		gr[B[i]].push_back(make_pair(A[i],D[i]));
	}
	st[0] = ++cnt;
	dfs(0);
}
int pdfs(int x)
{
	U[x] = V[x] = 1e16;
	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]]){
		int ne = 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 = ne;
	}

	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 = 1e16;
	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:117:2: warning: "/*" within comment [-Wcomment]
 }/**/
   
factories.cpp: In function 'void dfs(int)':
factories.cpp:35: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