Submission #643010

#	Time	Username	Problem	Language	Result	Execution time	Memory
643010		ymm	Factories (JOI14_factories)	C++17	100 / 100	2803 ms	188676 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 510'010;
const int lg = 19;
vector<pll> A0[N];
vector<int> ord;
int rmq[lg+1][2*N];
int st[N], ft[N], h[N];
ll dis[N];
int n;

void dfs(int v, int p, ll d, int h)
{
	::h[v] = h;
	st[v] = ord.size();
	ord.push_back(v);
	dis[v] = d;
	for (auto [u, w] : A0[v]) {
		if (u != p) {
			dfs(u, v, d + w, h+1);
			ord.push_back(v);
		}
	}
	ft[v] = ord.size();
}

#define HMIN(x, y) (h[x]<h[y]?(x):(y))

void rmq_init()
{
	int n = ord.size();
	Loop (i,0,n)
		rmq[0][i] = ord[i];
	{ vector<int> dard; ord.swap(dard); }
	Loop (i,0,lg)
		for (int j = 0; j + (2<<i) <= n; ++j)
			rmq[i+1][j] = HMIN(rmq[i][j], rmq[i][j+(1<<i)]);
}

pair<ll,int> get_dis(int x, int y)
{
	ll ans = dis[x] + dis[y];
	if (st[x] > st[y]) {
		int tmp = x;
		x = y;
		y = tmp;
	}
	x = st[x];
	y = st[y]+1;
	int l = __lg(y - x);
	int a = HMIN(rmq[l][x], rmq[l][y - (1<<l)]);
	ans -= 2*dis[a];
	return {ans, a};
}

void Init(int N, int X[], int Y[], int D[])
{
	n = N;
	Loop (i,0,n) {
		A0[X[i]].push_back({Y[i],D[i]});
		A0[Y[i]].push_back({X[i],D[i]});
	}
	dfs(0, 0, 0, 0);
	rmq_init();
	Loop (i,0,N) {
		vector<pll> dard;
		A0[i].swap(dard);
	}
}

ll dij(const vector<vector<pll>> &A, const vector<int> &x, const vector<int> &y)
{
	static ll dis[N];
	fill(dis, dis+A.size(), (ll)1e18);
	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	for (int v : x) {
		dis[v] = 0;
		q.push({0,v});
	}
	while (q.size()) {
		auto [d, v] = q.top();
		q.pop();
		if (d != dis[v])
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w < dis[u]) {
				dis[u] = d + w;
				q.push({dis[u], u});
			}
		}
	}
	ll ans = 1e18;
	for (int v : y)
		ans = min(ans, dis[v]);
	return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
	static bool imp_vis[N];
	vector<int> imp;
	Loop (i,0,S) {
		imp_vis[X[i]] = 1;
		imp.push_back(X[i]);
	}
	Loop (i,0,T) {
		imp_vis[Y[i]] = 1;
		imp.push_back(Y[i]);
	}
	if (!imp_vis[0]) {
		imp_vis[0] = 1;
		imp.push_back(0);
	}
	sort(imp.begin(), imp.end(), [](int v, int u){return st[v] < st[u];});
	int kooft_ = imp.size();
	Loop (i,1,kooft_) {
		int v = get_dis(imp[i], imp[i-1]).second;
		if (!imp_vis[v]) {
			imp_vis[v] = 1;
			imp.push_back(v);
		}
	}
	sort(imp.begin(), imp.end(), [](int v, int u){return st[v] < st[u];});
	vector<int> stk = {0};
	vector<vector<pll>> A(imp.size());
	Loop (i,1,imp.size()) {
		int v = imp[i];
		while (ft[imp[stk.back()]] <= st[v])
			stk.pop_back();
		ll d = get_dis(imp[stk.back()], v).first;
		A[stk.back()].push_back({i, d});
		A[i].push_back({stk.back(), d});
		stk.push_back(i);
	}
	for (auto v : imp)
		imp_vis[v] = 0;
	vector<int> x, y;
	static int dard1[N];
	Loop (i,0,imp.size())
		dard1[imp[i]] = i;
	Loop (i,0,S)
		x.push_back(dard1[X[i]]);
	Loop (i,0,T)
		y.push_back(dard1[Y[i]]);
	return dij(A, x, y);
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
factories.cpp:133:2: note: in expansion of macro 'Loop'
  133 |  Loop (i,1,imp.size()) {
      |  ^~~~
factories.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
factories.cpp:146:2: note: in expansion of macro 'Loop'
  146 |  Loop (i,0,imp.size())
      |  ^~~~

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