oj.uz

Submission #25264

# Submission time Handle Problem Language Result Execution time Memory
25264 2017-06-21T05:25:05 Z 김현수(#1059) Factories (JOI14_factories) C++11
0 / 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]], 0);
	return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 235364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 235232 KB Output isn't correct
2 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 -