Submission #388983

#	Time	Username	Problem	Language	Result	Execution time	Memory
388983		sinamhdv	Factories (JOI14_factories)	C++11	100 / 100	5779 ms	175040 KiB

factories

// JOI14_factories
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 500100
#define LOGN 25

int n;
vector<pii> adj[MAXN];
vector<pll> cld[MAXN];
ll h[MAXN];
int sttime[MAXN], fntime[MAXN], timer;
int col[MAXN];
ll dp[2][MAXN];
ll ans;
int lpar[LOGN][MAXN];
int eh[MAXN];

bool cmp(int x, int y)
{
	return sttime[x] < sttime[y];
}

int getlca(int u, int v)
{
	if (eh[u] > eh[v]) swap(u, v);
	FOR(i, 0, LOGN)
		if ((eh[v] - eh[u]) >> i & 1)
			v = lpar[i][v];
	if (u == v) return u;
	for (int i = LOGN - 1; i >= 0; i--)
		if (lpar[i][v] != lpar[i][u])
			u = lpar[i][u], v = lpar[i][v];
	return lpar[0][u];
}

void dfs1(int v, int par)
{
	sttime[v] = timer++;
	for (pii p : adj[v])
	{
		int u = p.fr;
		int w = p.sc;
		if (u == par) continue;
		h[u] = h[v] + w;
		lpar[0][u] = v;
		eh[u] = eh[v] + 1;
		dfs1(u, v);
	}
	fntime[v] = timer;
}

void dfs2(int v)
{
	if (col[v] == 1) dp[0][v] = 0;
	else if (col[v] == 2) dp[1][v] = 0;

	for (pll p : cld[v])
	{
		int u = p.fr;
		ll w = p.sc;
		dfs2(u);
		dp[0][v] = min(dp[0][v], dp[0][u] + w);
		dp[1][v] = min(dp[1][v], dp[1][u] + w);
	}

	ans = min(ans, dp[0][v] + dp[1][v]);
}

void Init(int N, int A[], int B[], int D[])
{
	n = N;
	FOR(i, 0, n - 1)
	{
		int a = A[i] + 1;
		int b = B[i] + 1;
		adj[a].pb({b, D[i]});
		adj[b].pb({a, D[i]});
	}

	dfs1(1, -1);

	FOR(i, 1, LOGN)
		FOR(j, 1, n + 1)
			lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];
}

ll Query(int s, int x[], int t, int y[])
{
	vector<int> vec;
	FOR(i, 0, s) vec.pb(x[i] + 1);
	FOR(i, 0, t) vec.pb(y[i] + 1);

	sort(all(vec), cmp);
	int k = vec.size();

	FOR(i, 1, k) vec.pb(getlca(vec[i], vec[i - 1]));
	sort(all(vec), cmp);
	vec.resize(unique(all(vec)) - vec.begin());

	// clear stuff
	for (int u : vec) cld[u].clear(), col[u] = 0, dp[0][u] = dp[1][u] = LINF;
	ans = LINF;

	vector<int> stk;
	for (int v : vec)
	{
		while (stk.size() && fntime[stk.back()] < fntime[v]) stk.pop_back();
		if (stk.size())
			cld[stk.back()].pb({v, h[v] - h[stk.back()]});
		stk.pb(v);
	}

	FOR(i, 0, s)
		col[x[i] + 1] = 1;
	FOR(i, 0, t)
		col[y[i] + 1] = 2;

	dfs2(vec[0]);

	return ans;
}

/*
int _x[MAXN], _y[MAXN];
int _a[MAXN], _b[MAXN], _d[MAXN];

int32_t main(void)
{
	fast_io;
	int n, q;
	cin >> n >> q;
	FOR(i, 0, n - 1)
		cin >> _a[i] >> _b[i] >> _d[i];

	Init(n, _a, _b, _d);

	FOR(i, 0, q)
	{
		int s, t;
		cin >> s >> t;
		FOR(j, 0, s)
			cin >> _x[j];
		FOR(j, 0, t)
			cin >> _y[j];

		cout << Query(s, _x, t, _y) << endl;
	}
	return 0;
}
*/

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