Submission #372218

#	Time	Username	Problem	Language	Result	Execution time	Memory
372218		MahdiBahramian	Factories (JOI14_factories)	C++11	100 / 100	4085 ms	121800 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
const int Max = 5e5 + 10;
const int LOG = 20;
const ll INF = 1e17 + 10;
int n;
vector<pair<int , int>> N[Max];
int sttime[Max] , edtime[Max] , ttime , par[Max][LOG] , h[Max];
ll dst[Max];

void DFS(int v , int p = 0)
{
	sttime[v] = ++ttime;
	for(int lg = 1 ; lg < LOG ; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
	for(pair<int , int> u : N[v]) if(u.F != p) h[u.F] = h[v] + 1 , par[u.F][0] = v , dst[u.F] = dst[v] + u.S , DFS(u.F , v);
	edtime[v] = ttime + 1;
}
int lca(int a , int b)
{
	//if(a == b) return a;
	if(h[a] < h[b]) swap(a , b);
	for(int lg = LOG ; lg-- ; ) if((h[a] - h[b]) & (1 << lg)) a = par[a][lg];
	if(a == b) return a;
	for(int lg = LOG ; lg-- ; ) if(par[a][lg] != par[b][lg]) a = par[a][lg] , b = par[b][lg];
	return par[a][0];
}
void Init(int N , int* A , int* B , int* D)
{
	n = N;
	for(int i = 0 ; i < n - 1 ; i++) ::N[A[i]].pb(mp(B[i] , D[i])) , ::N[B[i]].pb(mp(A[i] , D[i]));
	DFS(0);
}

ll DST[Max] , S[Max];

void dfs(vector<int> & verts)
{
	int R = 0; S[++R] = verts[0];
	for(int i = 1 ; i < verts.size() ; i++)
	{
		while(sttime[S[R]] > sttime[verts[i]] || edtime[S[R]] <= sttime[verts[i]])
		{
			DST[S[R]] = min(DST[S[R]] , DST[S[R - 1]] + dst[S[R]] - dst[S[R - 1]]);
			DST[S[R - 1]] = min(DST[S[R - 1]] , DST[S[R]] + dst[S[R]] - dst[S[R - 1]]);
			R--;
		}
		DST[S[R]] = min(DST[S[R]] , DST[verts[i]] + dst[verts[i]] - dst[S[R]]);
		DST[verts[i]] = min(DST[verts[i]] , DST[S[R]] + dst[verts[i]] - dst[S[R]]);
		S[++R] = verts[i];
	}
	while(R > 1)
	{
		DST[S[R]] = min(DST[S[R]] , DST[S[R - 1]] + dst[S[R]] - dst[S[R - 1]]);
		DST[S[R - 1]] = min(DST[S[R - 1]] , DST[S[R]] + dst[S[R]] - dst[S[R - 1]]);
		R--;
	}
}
long long Query(int S , int* X , int T , int* Y)
{
	vector<pair<int , int>> srt1 , srt2;
	for(int i = 0 ; i < S ; i++) srt1.pb(mp(sttime[X[i]] , X[i])) , srt2.pb(mp(sttime[X[i]] , X[i]));
	for(int i = 0 ; i < T ; i++) srt1.pb(mp(sttime[Y[i]] , Y[i])) , srt2.pb(mp(sttime[Y[i]] , Y[i]));
	sort(srt1.begin() , srt1.end());

	for(int i = 0 ; i < srt1.size() - 1 ; i++)
	{
		int l = lca(srt1[i].S , srt1[i + 1].S);
		srt2.pb(mp(sttime[l] , l));
	}
	{
		int l = lca(srt1[0].S , srt1.back().S);
		srt2.pb(mp(sttime[l] , l));
	}
	sort(srt2.begin() , srt2.end());
	vector<int> verts;
	for(pair<int , int> v : srt2) verts.pb(v.S) , DST[v.S] = INF;
	verts.resize(unique(verts.begin() , verts.end()) - verts.begin());
	for(int i = 0 ; i < S ; i++) DST[X[i]] = 0;
	dfs(verts);
	dfs(verts);
	ll ans = INF;
	for(int i = 0 ; i < T ; i++) ans = min(ans , DST[Y[i]]);
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(std::vector<int>&)':
factories.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 1 ; i < verts.size() ; i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0 ; i < srt1.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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