oj.uz

Submission #364334

# Submission time Handle Problem Language Result Execution time Memory
364334 2021-02-09T02:01:01 Z Kevin_Zhang_TW Factories (JOI14_factories) C++17
0 / 100
 8000 ms 114608 KB 
#include "factories.h"
#include <bits/stdc++.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] ];
}

long long Query(int S, int X[], int T, int Y[]) {
	ll res = inf;
	for (int i = 0;i < S;++i)
		for (int j = 0;j < T;++j) {
			int a = X[i], b = Y[j];
			chmin(res, dep[a] + dep[b] - 2 * dep[getlca(a, b)]);
		}
	return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 12524 KB Output is correct
2 Execution timed out 8042 ms 29164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12396 KB Output is correct
2 Correct 2336 ms 90628 KB Output is correct
3 Correct 7125 ms 101320 KB Output is correct
4 Correct 2187 ms 91364 KB Output is correct
5 Correct 5661 ms 114608 KB Output is correct
6 Correct 4963 ms 93488 KB Output is correct
7 Execution timed out 8036 ms 42312 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 12524 KB Output is correct
2 Execution timed out 8042 ms 29164 KB Time limit exceeded
3 Halted 0 ms 0 KB -