oj.uz

Submission #25307

# Submission time Handle Problem Language Result Execution time Memory
25307 2017-06-21T06:24:50 Z 김현수(#1059) Factories (JOI14_factories) C++11
15 / 100
 6000 ms 288004 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, L = 20;

ll n, s[N], e[N], inv[N], dep[N], frd[N], cc, ans;
ll par[L][N], dis[L][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;
	frd[C] = frd[P] + dis[0][C];
	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=L;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A];
		}
	}
	if(A == B) return A;
	for(ll i=L;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
		}
	}
	return par[0][A];
}

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<L;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 = frd[A] - frd[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 239272 KB Output is correct
2 Correct 1793 ms 239868 KB Output is correct
3 Correct 1829 ms 239672 KB Output is correct
4 Correct 1766 ms 239984 KB Output is correct
5 Correct 1106 ms 239908 KB Output is correct
6 Correct 1649 ms 239732 KB Output is correct
7 Correct 1783 ms 239672 KB Output is correct
8 Correct 1736 ms 239980 KB Output is correct
9 Correct 1129 ms 239908 KB Output is correct
10 Correct 1613 ms 239732 KB Output is correct
11 Correct 1943 ms 239672 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 239140 KB Output is correct
2 Execution timed out 6000 ms 279260 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

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