oj.uz

Submission #122613

# Submission time Handle Problem Language Result Execution time Memory
122613 2019-06-28T19:06:15 Z tinder Factories (JOI14_factories) C++14
100 / 100
 6954 ms 157492 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define v first
#define w second

const int maxn = 5e5 + 5;
using ll = long long;
using ii = pair<ll, ll>;

int N;
vector<ii> g[maxn], t[maxn];
int in[maxn], tym;
int lvl[maxn], dp[20][maxn];
ll dist[maxn];
ll f[maxn];
bool done[maxn];

void dfs(int u, int p, ll dd) {
	if(p == -1) lvl[u] = 0;
	else lvl[u] = lvl[p] + 1;
	dist[u] = dd;

	dp[0][u] = p;
	for(int i = 1; i <= 18; i++) {
		int mid = dp[i - 1][u];
		if(mid != -1) dp[i][u] = dp[i - 1][mid];
		else break;
	}

	in[u] = tym++;

	for(ii e : g[u]) {
		if(e.v != p) {
			dfs(e.v, u, e.w + dd);
		}
	}
}

int __lca(int u, int v) {
	if(lvl[u] > lvl[v]) swap(u, v);
	int d = lvl[v] - lvl[u];
	for(int i = 0; i < 19; i++) {
		if(d & (1 << i)) {
			v = dp[i][v];
		}
	}
	if(u == v) return u;
	for(int i = 18; i >= 0; i--) {
		if(dp[i][u] != dp[i][v]) {
			u = dp[i][u];
			v = dp[i][v];
		}
	}
	return dp[0][u];
}

void Init(int _N, int A[], int B[], int D[]) {
	N = _N;
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i], w = D[i];
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	memset(dp, -1, sizeof dp);
	dfs(0, -1, 0LL);
}

long long Query(int S, int X[], int T, int Y[]) {
	// find nodes
	vector<int> all;
	for(int i = 0; i < S; i++) {
		all.emplace_back(X[i]);
	}
	for(int i = 0; i < T; i++) {
		all.emplace_back(Y[i]);
	}
	sort(all.begin(), all.end(), [](int x, int y){ return in[x] < in[y]; });
	all.erase(unique(all.begin(), all.end()), all.end());
	int sz = all.size();
	for(int i = 1; i < sz; i++) {
		all.emplace_back(__lca(all[i - 1], all[i]));
	}
	sort(all.begin(), all.end(), [](int x, int y){ return in[x] < in[y]; });
	all.erase(unique(all.begin(), all.end()), all.end());

	// clear
	for(int u : all) {
		t[u].clear();
		f[u] = 1e18;
		done[u] = false;
	}

	// build tree
	for(int i = 1; i < all.size(); i++) {
		int u = __lca(all[i - 1], all[i]);
		int v = all[i];
		ll w = dist[v] - dist[u];
		t[u].emplace_back(ii(v, w));
		t[v].emplace_back(ii(u, w));
	}

	// Dijkstra
	priority_queue<ii, vector<ii>, greater<ii>> Q;
	for(int i = 0; i < S; i++) {
		f[X[i]] = 0;
		Q.emplace(0, X[i]);
	}
	while(Q.size()) {
		int u = Q.top().second;
		Q.pop();
		if(done[u]) continue;
		done[u] = true;
		for(ii &e : t[u]) {
			if(f[e.v] > f[u] + e.w) {
				f[e.v] = f[u] + e.w;
				Q.emplace(f[e.v], e.v);
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < T; i++) {
		ans = min(ans, f[Y[i]]);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < all.size(); i++) {
                 ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 63480 KB Output is correct
2 Correct 1608 ms 71900 KB Output is correct
3 Correct 1855 ms 71720 KB Output is correct
4 Correct 1587 ms 72092 KB Output is correct
5 Correct 1250 ms 72056 KB Output is correct
6 Correct 1128 ms 71928 KB Output is correct
7 Correct 2090 ms 71916 KB Output is correct
8 Correct 1652 ms 71928 KB Output is correct
9 Correct 1253 ms 72184 KB Output is correct
10 Correct 1194 ms 71800 KB Output is correct
11 Correct 1864 ms 71764 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 63096 KB Output is correct
2 Correct 2652 ms 128620 KB Output is correct
3 Correct 3730 ms 130680 KB Output is correct
4 Correct 1764 ms 126036 KB Output is correct
5 Correct 2627 ms 154420 KB Output is correct
6 Correct 3367 ms 132492 KB Output is correct
7 Correct 2888 ms 85496 KB Output is correct
8 Correct 1503 ms 85092 KB Output is correct
9 Correct 1715 ms 90104 KB Output is correct
10 Correct 2764 ms 86616 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 63480 KB Output is correct
2 Correct 1608 ms 71900 KB Output is correct
3 Correct 1855 ms 71720 KB Output is correct
4 Correct 1587 ms 72092 KB Output is correct
5 Correct 1250 ms 72056 KB Output is correct
6 Correct 1128 ms 71928 KB Output is correct
7 Correct 2090 ms 71916 KB Output is correct
8 Correct 1652 ms 71928 KB Output is correct
9 Correct 1253 ms 72184 KB Output is correct
10 Correct 1194 ms 71800 KB Output is correct
11 Correct 1864 ms 71764 KB Output is correct
12 Correct 56 ms 63096 KB Output is correct
13 Correct 2652 ms 128620 KB Output is correct
14 Correct 3730 ms 130680 KB Output is correct
15 Correct 1764 ms 126036 KB Output is correct
16 Correct 2627 ms 154420 KB Output is correct
17 Correct 3367 ms 132492 KB Output is correct
18 Correct 2888 ms 85496 KB Output is correct
19 Correct 1503 ms 85092 KB Output is correct
20 Correct 1715 ms 90104 KB Output is correct
21 Correct 2764 ms 86616 KB Output is correct
22 Correct 5942 ms 140056 KB Output is correct
23 Correct 5156 ms 138948 KB Output is correct
24 Correct 6303 ms 143000 KB Output is correct
25 Correct 6435 ms 144140 KB Output is correct
26 Correct 5984 ms 136276 KB Output is correct
27 Correct 4209 ms 157492 KB Output is correct
28 Correct 3790 ms 134708 KB Output is correct
29 Correct 6170 ms 135056 KB Output is correct
30 Correct 6313 ms 134716 KB Output is correct
31 Correct 6954 ms 135000 KB Output is correct
32 Correct 2118 ms 91564 KB Output is correct
33 Correct 1900 ms 88156 KB Output is correct
34 Correct 2775 ms 84792 KB Output is correct
35 Correct 2796 ms 84596 KB Output is correct
36 Correct 3015 ms 85240 KB Output is correct
37 Correct 3374 ms 85104 KB Output is correct