Submission #335676

#	Time	Username	Problem	Language	Result	Execution time	Memory
335676		GioChkhaidze	Factories (JOI14_factories)	C++14	0 / 100	58 ms	49004 KiB

factories

#include <bits/stdc++.h> 
#include "factories.h"

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int U=5e5+5;

bool f[U];
ll d[U],Dist[U];
int P[U][21];
int depth,dep[U];
int timer,in[U],out[U];

vector < int > rec,ver;
vector < pair < int , ll > > g[U]; 
vector < pair < int , int  > > v[U];
priority_queue < pair < ll , int > > pq;

bool is_anc(int a,int b) {
	return (in[a]<=in[b] && out[b]<=out[a]);
}

inline int LCA(int a,int b) {
	if (dep[a]>dep[b]) swap(a,b);
	if (is_anc(a,b)) return a;
	for (int i=19; i>=0; i--) 
		if (!is_anc(P[a][i],b)) a=P[a][i];
	return P[a][0];
}

void Dfs(int x,int p,ll dist) {
	in[x]=++timer;
	dep[x]=++depth;
	d[x]=dist;
	P[x][0]=p;
	
	int to,cost;
	for (int i=0; i<v[x].size(); i++) {
		to=v[x][i].F;
		cost=v[x][i].S;
		if (to!=p) Dfs(to,x,dist+cost);
	}
	
	out[x]=timer;
	--depth;
}

void Init(int n, int a[], int b[], int c[]) {
	for (int i=0; i<n; i++) {
		v[a[i]].pb({b[i],c[i]});
		v[b[i]].pb({a[i],c[i]});
	}
	
	Dfs(0,0,0);
	for (int j=1; j<=19; j++)
		for (int i=1; i<=n; i++)
			P[i][j]=P[P[i][j-1]][j-1];
}

bool cmp(int a,int b) {
	return in[a]<in[b];
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i=0; i<S; i++) {
		ver.pb(X[i]);
	}
	
	for (int i=0; i<T; i++) {
		ver.pb(Y[i]);
	}
	
	sort(ver.begin(),ver.end(),cmp);
	
	ll dist;
	int vert;
	for (int i=0; i<S+T; i++) {
		if (!i) continue;
		vert=LCA(ver[i-1],ver[i]);
		ver.pb(in[vert]);
	}
	
	sort(ver.begin(),ver.end(),cmp);
	
	vert=ver[0];
	for (int i=1; i<ver.size(); i++) {
		if (ver[i]==ver[i-1]) continue;
		if (ver[i]==vert) continue;
		assert(ver[i]!=vert);

		while (!(is_anc(vert,ver[i]))) {
			vert=rec.back();
			rec.pop_back();	
		}
			
		dist=d[ver[i]]-d[vert];
		g[vert].pb({ver[i],dist});
		g[ver[i]].pb({vert,dist});
		rec.pb(vert);
		vert=ver[i];
	}
	
	while (rec.size()) 
		rec.pop_back();

	for (int i=0; i<ver.size(); i++) {
		if (i && ver[i]==ver[i-1]) continue;
		Dist[ver[i]]=1e15;
	}
	
	for (int i=0; i<S; i++) {
		Dist[X[i]]=0;
	}
	
	for (int i=0; i<ver.size(); i++) {
		if (i && ver[i]==ver[i-1]) continue;
		pq.push({-Dist[ver[i]],ver[i]});
	}
	
	int to,x;
	ll cost;
	while (!pq.empty()) {
		x=pq.top().S;
		pq.pop();
		if (f[x]) continue;
		f[x]=true;
		for (int i=0; i<g[x].size(); i++) {
			to=g[x][i].F;
			cost=g[x][i].S;
			if (!f[to] && Dist[x]+cost<Dist[to]) {
				Dist[to]=Dist[x]+cost;
				pq.push({-Dist[to],to});
			}
		}
	}
	
	ll ans=1e15;
	for (int i=0; i<T; i++) {
		ans=min(ans,Dist[Y[i]]);
	}
	
	for (int i=0; i<ver.size(); i++) {
		g[ver[i]].clear();
		f[ver[i]]=false;
		Dist[ver[i]]=0;
	}
	
	ver.clear();
  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void Dfs(int, int, long long int)':
factories.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i=0; i<v[x].size(); i++) {
      |                ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i=1; i<ver.size(); i++) {
      |                ~^~~~~~~~~~~
factories.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int i=0; i<ver.size(); i++) {
      |                ~^~~~~~~~~~~
factories.cpp:120:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i=0; i<ver.size(); i++) {
      |                ~^~~~~~~~~~~
factories.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i=0; i<g[x].size(); i++) {
      |                 ~^~~~~~~~~~~~
factories.cpp:147:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for (int i=0; i<ver.size(); i++) {
      |                ~^~~~~~~~~~~

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