oj.uz

Submission #33041

# Submission time Handle Problem Language Result Execution time Memory
33041 2017-10-19T04:52:52 Z aome Factories (JOI14_factories) C++14
15 / 100
 6000 ms 141192 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

const int N = 500005;
const long long INF = 1e18;

typedef pair<int, int> ii;

int n, h[N];
int cnt, st[N];
int par[20][N];
long long res;
long long dis[N];
long long f[2][N];
bool flag[2][N];
vector<ii> G[N];

void dfs(int u) {
	st[u] = cnt++;
	for (auto v : G[u]) {
		if (par[0][u] == v.first) continue;
		par[0][v.first] = u, dis[v.first] = dis[u] + v.second;
		h[v.first] = h[u] + 1, dfs(v.first);
	}
}

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 18; i >= 0; --i) {
		if (h[par[i][v]] >= h[u]) v = par[i][v];
	}
	for (int i = 18; i >= 0; --i) {
		if (par[i][v] != par[i][u]) {
			v = par[i][v], u = par[i][u];
		}
	}
	return (u == v) ? u : par[0][u];
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < (n - 1); ++i) {
		G[a[i]].push_back(ii(b[i], d[i]));
		G[b[i]].push_back(ii(a[i], d[i]));
	}
	dfs(0);
	for (int i = 1; i <= 18; ++i) {
		for (int j = 1; j <= n; ++j) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
}

int ver[N * 8];
vector<int> nG[N];

void solve(int u) {
	for (int i = 0; i < 2; ++i) {
		if (flag[i][u]) f[i][u] = min(f[i][u], dis[u]);
	}
	for (auto v : nG[u]) {
		solve(v);
		for (int i = 0; i < 2; ++i) f[i][u] = min(f[i][u], f[i][v]);
	}
	long long mn[2];
	mn[0] = mn[1] = INF;
	for (auto v : nG[u]) {
		for (int i = 0; i < 2; ++i) {
			res = min(res, f[i][v] + mn[i ^ 1] - 2 * dis[u]);
		}
		for (int i = 0; i < 2; ++i) {
			mn[i] = min(mn[i], f[i][v]);
		}
	}
	for (int i = 0; i < 2; ++i) {
		if (flag[i ^ 1][u]) res = min(res, mn[i] - dis[u]);
	}
}

long long Query(int s, int x[], int t, int y[]) {
	int sz = 0;
	for (int i = 0; i < s; ++i) ver[sz++] = x[i], flag[0][x[i]] = 1;
	for (int i = 0; i < t; ++i) ver[sz++] = y[i], flag[1][y[i]] = 1;
	sort(ver, ver + sz, [&](int x, int y) {
		return st[x] < st[y];
	});
	int cur = sz;
	for (int i = 1; i < cur; ++i) {
		ver[sz++] = lca(ver[i - 1], ver[i]);
	}
	sort(ver, ver + sz, [&](int x, int y) {
		return st[x] < st[y];
	});
	for (int i = 1; i < sz; ++i) {
		int p = lca(ver[i - 1], ver[i]);
		if (p != ver[i]) nG[p].push_back(ver[i]);
		// cout << p << ' ' << ver[i] << '\n';
	}
	for (int i = 0; i < sz; ++i) {
		f[0][ver[i]] = f[1][ver[i]] = INF;
	}
	res = INF, solve(ver[0]);
	for (int i = 0; i < sz; ++i) {
		flag[0][ver[i]] = flag[1][ver[i]] = 0;
		nG[ver[i]].clear();
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 119016 KB Output is correct
2 Correct 3673 ms 119280 KB Output is correct
3 Correct 4109 ms 119280 KB Output is correct
4 Correct 3763 ms 119280 KB Output is correct
5 Correct 3533 ms 119364 KB Output is correct
6 Correct 2919 ms 119316 KB Output is correct
7 Correct 3976 ms 119280 KB Output is correct
8 Correct 3676 ms 119280 KB Output is correct
9 Correct 3173 ms 119368 KB Output is correct
10 Correct 2659 ms 119316 KB Output is correct
11 Correct 3776 ms 119280 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 119016 KB Output is correct
2 Execution timed out 6000 ms 137760 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 141192 KB Execution timed out
2 Halted 0 ms 0 KB -