oj.uz

Submission #25295

# Submission time Handle Problem Language Result Execution time Memory
25295 2017-06-21T06:03:14 Z 김현수(#1059) Factories (JOI14_factories) C++11
15 / 100
 6000 ms 284096 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18, N = 500005;

ll n, s[N], e[N], inv[N], dep[N], cc, ans;
ll par[20][N], dis[20][N], dt[3][N], typ[N];

vector<pll> adj[N], tmp[N];

void calc (ll C, ll P) {
	s[C] = ++cc;
	dep[C] = dep[P] + 1;
	inv[cc] = C;
	for(auto &T : adj[C]) {
		ll A, B; tie(A, B) = T;
		if(A == P) continue;
		par[0][A] = C;
		dis[0][A] = B;
		calc(A, C);
	}
	e[C] = cc;
}

ll getlca (ll A, ll B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(ll i=20;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A];
		}
	}
	if(A == B) return A;
	for(ll i=20;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
		}
	}
	return par[0][A];
}

ll getdist (ll A, ll B) {
	if(dep[A] < dep[B]) swap(A, B);
	ll R = 0;
	for(ll i=20;i--;) {
		if(dep[A] - dep[B] >= (1<<i)){
			R += dis[i][A]; A = par[i][A];
		}
	}
	return R;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(ll i=0;i<n-1;i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	calc(0, 0);
	for(ll k=1;k<20;k++) {
		for(ll i=0;i<n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
			dis[k][i] = dis[k-1][i] + dis[k-1][par[k-1][i]];
		}
	}
}

void dfs (ll C, ll P) {
	dt[1][C] = dt[2][C] = inf;
	dt[typ[C]][C] = 0;
	for(auto &T : tmp[C]) {
		ll A, B; tie(A, B) = T;
		if(A == P) continue;
		dfs(A, C);
		dt[1][C] = min(dt[1][C], dt[1][A] + B);
		dt[2][C] = min(dt[2][C], dt[2][A] + B);
	}
	ans = min(ans, dt[1][C]+dt[2][C]);
}

ll Query(int C1, int X[], int C2, int Y[]) {
	vector<ll> V, S;
	for(ll i=0;i<C1;i++) {
		V.push_back(s[X[i]]);
		typ[X[i]] = 1;
	}
	for(ll i=0;i<C2;i++) {
		V.push_back(s[Y[i]]);
		typ[Y[i]] = 2;
	}
	sort(V.begin(), V.end());
	for(ll i=1;i<C1+C2;i++) {
		ll A = inv[V[i-1]], B = inv[V[i]];
		V.push_back(s[getlca(A, B)]);
	}
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for(auto &T : V) tmp[inv[T]].clear();
	for(auto &T : V) {
		ll A = inv[T];
		while(!S.empty()) {
			ll P = S.back();
			if(s[P] <= s[A] && e[A] <= e[P]) break;
			else S.pop_back();
		}
		if(!S.empty()) {
			ll P = S.back(), D = getdist(A, P);
			tmp[A].push_back({P, D});
			tmp[P].push_back({A, D});
		}
		S.push_back(A);
	}
	ans = inf;
	dfs(inv[V[0]], inv[V[0]]);
	for(auto &T : V) typ[inv[T]] = 0;
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 235364 KB Output is correct
2 Correct 1846 ms 235960 KB Output is correct
3 Correct 2119 ms 235764 KB Output is correct
4 Correct 1906 ms 236076 KB Output is correct
5 Correct 1166 ms 235996 KB Output is correct
6 Correct 1616 ms 235824 KB Output is correct
7 Correct 1993 ms 235764 KB Output is correct
8 Correct 1856 ms 236072 KB Output is correct
9 Correct 1109 ms 235996 KB Output is correct
10 Correct 1599 ms 235824 KB Output is correct
11 Correct 2029 ms 235764 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 235232 KB Output is correct
2 Correct 5869 ms 275608 KB Output is correct
3 Execution timed out 6000 ms 278120 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 284096 KB Execution timed out
2 Halted 0 ms 0 KB -