oj.uz

Submission #364339

# Submission time Handle Problem Language Result Execution time Memory
364339 2021-02-09T02:20:55 Z Kevin_Zhang_TW Factories (JOI14_factories) C++17
100 / 100
 7120 ms 117052 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) {  cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 500010, LG = 19;
const ll inf = 1ll << 55;

ll dep[MAX_N];
int anc[LG][MAX_N], in[MAX_N], out[MAX_N], n;
vector<pair<int,int>> edge[MAX_N];

void dfs1(int x, int lst) {
	static int t;
	in[x] = ++t;
	for (auto [u, w] : edge[x]) if (u != lst) {
		anc[0][u] = x;
		dep[u] = dep[x] + w;
		dfs1(u, x);
	}
	out[x] = t;
}
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
int getlca(int a, int b) { 
	for (int d = LG-1;d >= 0;--d)
		if (!isanc(anc[d][a], b))
			a = anc[d][a];
	return isanc(a, b) ? a : anc[0][a];
}
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0;i < N-1;++i) {
		int a = A[i], b = B[i], c = D[i];
		edge[a].pb(b, c);
		edge[b].pb(a, c);
	}
	dfs1(0, 0);
	for (int d = 1;d < LG;++d)
		for (int i = 0;i < N;++i)
			anc[d][i] = anc[d-1][ anc[d-1][i] ];
}
struct conf {
	int vis[MAX_N], time;
	void reset() { ++time; }
	void insert(int i) { vis[i] = time; }
	int count(int i) { return vis[i] == time; }
}svis, tvis;

long long Query(int S, int X[], int T, int Y[]) {
	ll res = inf;
	svis.reset(), tvis.reset();
	for (int i = 0;i < S;++i)
		svis.insert(X[i]);
	for (int i = 0;i < T;++i)
		tvis.insert(Y[i]);

	vector<int> loc(X, X+S); loc.insert(end(loc), Y, Y+T);
	sort(AI(loc), [&](int a, int b) { 
			return in[a] < in[b]; });
	loc.resize(unique(AI(loc)) - begin(loc));

	{
		int os = loc.size();
		for (int i = 0;i + 1 < os;++i) 
			loc.pb(getlca(loc[i], loc[i+1]));
	}

	sort(AI(loc), [&](int a, int b) { 
			return in[a] < in[b]; });
	loc.resize(unique(AI(loc)) - begin(loc));

	vector<int> stk;
	vector<pair<ll,ll>> dp;

	auto update = [&](int a, int b) {
		auto &[a0, a1] = dp[a];
		auto &[b0, b1] = dp[b];
		chmin(res, a0 + b1 - 2 * dep[stk[a]]);
		chmin(res, a1 + b0 - 2 * dep[stk[a]]);
		chmin(a0, b0), chmin(a1, b1);
	};
//	DE(S), debug(X, X+S);
//	DE(T), debug(Y, Y+T);
	for (int x : loc) {
		while (stk.size() > 1) {
			if (isanc(stk.back(), x)) break;
			update(stk.size() - 2, stk.size() - 1);
			stk.pop_back(), dp.pop_back();
		}
		stk.pb(x);
		dp.pb(inf, inf);
		if (svis.count(x)) dp.back().first = dep[x];
		if (tvis.count(x)) dp.back().second = dep[x];
		//DE(x, dp.back().first, dp.back().second, svis.count(x), tvis.count(x));

	}
	while (stk.size() > 1) {
		update(stk.size() - 2, stk.size() - 1);
		stk.pop_back(), dp.pop_back();
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12652 KB Output is correct
2 Correct 1207 ms 21240 KB Output is correct
3 Correct 1185 ms 29420 KB Output is correct
4 Correct 1184 ms 29548 KB Output is correct
5 Correct 1196 ms 29856 KB Output is correct
6 Correct 939 ms 29548 KB Output is correct
7 Correct 1154 ms 29420 KB Output is correct
8 Correct 1175 ms 29696 KB Output is correct
9 Correct 1191 ms 30024 KB Output is correct
10 Correct 903 ms 29568 KB Output is correct
11 Correct 1184 ms 29548 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 3110 ms 92528 KB Output is correct
3 Correct 3786 ms 94172 KB Output is correct
4 Correct 2710 ms 93524 KB Output is correct
5 Correct 3976 ms 116844 KB Output is correct
6 Correct 4001 ms 95576 KB Output is correct
7 Correct 3850 ms 36932 KB Output is correct
8 Correct 3153 ms 44156 KB Output is correct
9 Correct 3764 ms 47000 KB Output is correct
10 Correct 3966 ms 44740 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12652 KB Output is correct
2 Correct 1207 ms 21240 KB Output is correct
3 Correct 1185 ms 29420 KB Output is correct
4 Correct 1184 ms 29548 KB Output is correct
5 Correct 1196 ms 29856 KB Output is correct
6 Correct 939 ms 29548 KB Output is correct
7 Correct 1154 ms 29420 KB Output is correct
8 Correct 1175 ms 29696 KB Output is correct
9 Correct 1191 ms 30024 KB Output is correct
10 Correct 903 ms 29568 KB Output is correct
11 Correct 1184 ms 29548 KB Output is correct
12 Correct 11 ms 12396 KB Output is correct
13 Correct 3110 ms 92528 KB Output is correct
14 Correct 3786 ms 94172 KB Output is correct
15 Correct 2710 ms 93524 KB Output is correct
16 Correct 3976 ms 116844 KB Output is correct
17 Correct 4001 ms 95576 KB Output is correct
18 Correct 3850 ms 36932 KB Output is correct
19 Correct 3153 ms 44156 KB Output is correct
20 Correct 3764 ms 47000 KB Output is correct
21 Correct 3966 ms 44740 KB Output is correct
22 Correct 5883 ms 97020 KB Output is correct
23 Correct 5632 ms 99576 KB Output is correct
24 Correct 6484 ms 99160 KB Output is correct
25 Correct 6522 ms 100900 KB Output is correct
26 Correct 7120 ms 96672 KB Output is correct
27 Correct 6956 ms 117052 KB Output is correct
28 Correct 4719 ms 99012 KB Output is correct
29 Correct 7013 ms 96092 KB Output is correct
30 Correct 7034 ms 95468 KB Output is correct
31 Correct 6983 ms 96076 KB Output is correct
32 Correct 3954 ms 45768 KB Output is correct
33 Correct 2983 ms 42024 KB Output is correct
34 Correct 3713 ms 37740 KB Output is correct
35 Correct 3969 ms 37868 KB Output is correct
36 Correct 4006 ms 38360 KB Output is correct
37 Correct 3920 ms 38336 KB Output is correct