제출 #969739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969739		starchan	공장들 (JOI14_factories)	C++17	100 / 100	5133 ms	212208 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define in array<ll, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int	 MX			 =		        5e5+5;
const int	 LOGM		 =			       19;
const ll	 INF		 =	             1e18;

vector<ll> d(MX, INF);

vector<in> adj[MX], edge[MX];
int pa[LOGM][MX];
int tin[MX], tout[MX];

ll dep[MX];

int timer; 

void dfs(int u, ll lvl)
{
	tin[u] = ++timer;
	dep[u] = lvl;
	for(int i = 1; i < LOGM; i++)
		pa[i][u] = pa[i-1][pa[i-1][u]];
	for(auto [v, w]: adj[u])
	{
		if(v == pa[0][u])
			continue;
		pa[0][v] = u;
		dfs(v, lvl+w);
	}
	tout[u] = timer;
	return;
}

int lca(int u, int v)
{
	if(tin[u] >= tin[v])
		swap(u, v);
	if(tout[u] >= tout[v])
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int p = pa[i][u];
		if(tout[p] >= tout[v])
			continue;
		u = p;
	}
	return pa[0][u];
}

void Init(int n, int a[], int b[], int d[])
{
	for(int i = 0; i < n-1; i++)
	{
		adj[a[i]+1].pb({b[i]+1, d[i]});
		adj[b[i]+1].pb({a[i]+1, d[i]});
	}

	timer = 0;
	tin[0] = -1; tout[0] = n+1;
	pa[0][0] = 0; pa[0][1] = 0;
	dfs(1, 0);
	return;
}

ll Query(signed a, signed X[], signed b, signed Y[])
{
	for(int i = 0; i < a; i++)
		X[i]++;
	for(int i = 0; i < b; i++)
		Y[i]++;
	priority_queue<in> pq;

	vector<in> vv;
	for(int i = 0; i < a; i++)
	{
		d[X[i]] = 0;
		pq.push({0ll, X[i]});
		vv.pb({tin[X[i]], X[i]});
	}
	for(int i = 0; i < b; i++)
		vv.pb({tin[Y[i]], Y[i]});
	sort(vv.begin(), vv.end());
	for(int i = 1; i < (a+b); i++)
	{
		int w = lca(vv[i][1], vv[i-1][1]);
		vv.pb({tin[w], w});
	}


	vector<int> path;
	sort(vv.begin(), vv.end()); path.pb(vv[0][1]);
	for(int i = 1; i < vv.size(); i++)
	{
		while(tout[path.back()] < tout[vv[i][1]])
			path.pob();
		int u =	path.back();
		int v = vv[i][1];
		path.pb(v);
		edge[u].pb({v, dep[v]-dep[u]});
		edge[v].pb({u, dep[v]-dep[u]});
	}

	while(pq.size())
	{
		auto [W, u] = pq.top(); W = -W;
		pq.pop();
		if(d[u] < W)
			continue;
		for(auto [v, w]: edge[u])
		{
			if(d[v] > (d[u] + w))
			{
				d[v] = d[u] + w;
				pq.push({-d[v], v});
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < b; i++)
		ans = min(ans, d[Y[i]]);
	for(auto [t, W]: vv)
	{
		d[W] = INF;
		edge[W].clear();
	} 
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 1; i < vv.size(); i++)
      |                 ~~^~~~~~~~~~~

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