Submission #372068

#	Time	Username	Problem	Language	Result	Execution time	Memory
372068		MahdiBahramian	Factories (JOI14_factories)	C++11	0 / 100	31 ms	12800 KiB

factories

#include<bits/stdc++.h>
#include"factories.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(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 num , int A[] , int B[] , int D[])
{
	n = num;
	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]]) 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];
	}
}
ll 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());

	//cout << "**  ";
	//for(auto v : srt1) cout << v.S << ' '; cout << '\n';
	//cout << "*** ";
	for(int i = 0 ; i < srt1.size() - 1 ; i++)
	{
		int l = lca(srt1[i].F , srt1[i + 1].F);
		srt2.pb(mp(sttime[l] , l));
		//cout << l << ' ';
	}//cout << '\n';
	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;
}
/*
int A[Max] , B[Max] , D[Max] , X[Max] , Y[Max];

int main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int n , q; cin >> n >> q;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		cin >> A[i] >> B[i] >> D[i];
	}
	Init(n , A , B , D);
	for(int i = 0 ; i < q ; i++)
	{
		int s , t; cin >> s >> t;
		for(int i = 0 ; i < s ; i++) cin >> X[i];
		for(int i = 0 ; i < t ; i++) cin >> Y[i];
		cout << Query(s , X , t , Y) << '\n';
	}
}
*/

Compilation message (stderr)

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

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