oj.uz

Submission #388983

# Submission time Handle Problem Language Result Execution time Memory
388983 2021-04-13T12:20:53 Z sinamhdv Factories (JOI14_factories) C++11
100 / 100
 5779 ms 175040 KB 
// 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24612 KB Output is correct
2 Correct 1247 ms 42488 KB Output is correct
3 Correct 1236 ms 42636 KB Output is correct
4 Correct 1244 ms 42724 KB Output is correct
5 Correct 1118 ms 42896 KB Output is correct
6 Correct 862 ms 42608 KB Output is correct
7 Correct 1218 ms 42620 KB Output is correct
8 Correct 1213 ms 42624 KB Output is correct
9 Correct 1106 ms 43076 KB Output is correct
10 Correct 838 ms 42616 KB Output is correct
11 Correct 1222 ms 42608 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24204 KB Output is correct
2 Correct 2594 ms 142580 KB Output is correct
3 Correct 3566 ms 146276 KB Output is correct
4 Correct 1739 ms 124696 KB Output is correct
5 Correct 3117 ms 167532 KB Output is correct
6 Correct 3758 ms 129756 KB Output is correct
7 Correct 3611 ms 60356 KB Output is correct
8 Correct 1943 ms 60100 KB Output is correct
9 Correct 2438 ms 67224 KB Output is correct
10 Correct 3526 ms 61320 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24612 KB Output is correct
2 Correct 1247 ms 42488 KB Output is correct
3 Correct 1236 ms 42636 KB Output is correct
4 Correct 1244 ms 42724 KB Output is correct
5 Correct 1118 ms 42896 KB Output is correct
6 Correct 862 ms 42608 KB Output is correct
7 Correct 1218 ms 42620 KB Output is correct
8 Correct 1213 ms 42624 KB Output is correct
9 Correct 1106 ms 43076 KB Output is correct
10 Correct 838 ms 42616 KB Output is correct
11 Correct 1222 ms 42608 KB Output is correct
12 Correct 18 ms 24204 KB Output is correct
13 Correct 2594 ms 142580 KB Output is correct
14 Correct 3566 ms 146276 KB Output is correct
15 Correct 1739 ms 124696 KB Output is correct
16 Correct 3117 ms 167532 KB Output is correct
17 Correct 3758 ms 129756 KB Output is correct
18 Correct 3611 ms 60356 KB Output is correct
19 Correct 1943 ms 60100 KB Output is correct
20 Correct 2438 ms 67224 KB Output is correct
21 Correct 3526 ms 61320 KB Output is correct
22 Correct 4881 ms 134920 KB Output is correct
23 Correct 4424 ms 136452 KB Output is correct
24 Correct 4664 ms 140060 KB Output is correct
25 Correct 5051 ms 149164 KB Output is correct
26 Correct 5774 ms 138448 KB Output is correct
27 Correct 4154 ms 175040 KB Output is correct
28 Correct 3005 ms 158072 KB Output is correct
29 Correct 5779 ms 155252 KB Output is correct
30 Correct 5753 ms 154888 KB Output is correct
31 Correct 5759 ms 155268 KB Output is correct
32 Correct 2204 ms 69628 KB Output is correct
33 Correct 1960 ms 62936 KB Output is correct
34 Correct 2941 ms 59276 KB Output is correct
35 Correct 2837 ms 58916 KB Output is correct
36 Correct 3087 ms 60152 KB Output is correct
37 Correct 3077 ms 59900 KB Output is correct