oj.uz

Submission #83776

# Submission time Handle Problem Language Result Execution time Memory
83776 2018-11-10T13:14:15 Z jcg Factories (JOI14_factories) C++14
15 / 100
 2134 ms 525312 KB 
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/algorithm>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

typedef long long ll;

const ll oo = 0x3f3f3f3f3f3f3f3f;

vector<vector<pair<int, ll>>> adj;
vector<vector<pair<ll, int>>> table;
vector<int> tour, in, out, id;
vector<ll> depth;
vector<bool> inA, inB;

void Init(int N, int A[], int B[], int D[])
{
	adj.clear();
	adj.resize(N);

	for (int i = 0; i < N - 1; ++i)
	{
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}

	tour.clear();
	in = out = id = vector<int>(N);
	depth = vector<ll>(N);
	inA = inB = vector<bool>(N);

	function<void(int, int, ll)> dfs = [&](int u, int p, ll d)
	{
		in[u] = tour.size();
		depth[u] = d;
		tour.push_back(u);

		for (auto &e : adj[u])
			if (e.first != p)
			{
				dfs(e.first, u, d + e.second);
				tour.push_back(u);
			}

		out[u] = tour.size();
	};

	dfs(0, -1, 0);

	int logn = __lg(tour.size());

	table = vector<vector<pair<ll, int>>>(logn + 1, vector<pair<ll, int>>(tour.size()));

	for (int i = 0; i < tour.size(); ++i)
		table[0][i] = make_pair(depth[tour[i]], tour[i]);

	for (int i = 0; i < logn; ++i)
		for (int j = 0; j + (1 << i) < tour.size(); ++j)
			table[i + 1][j] = min(table[i][j], table[i][j + (1 << i)]);
}

bool ancestor(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
};

int lca(int u, int v)
{
	if (in[u] > in[v])
		swap(u, v);
	int l = __lg(in[v] - in[u]);
	return u == v ? u : min(table[l][in[u]], table[l][in[v] - (1 << l)]).second;
};

long long Query(int S, int X[], int T, int Y[])
{
	vector<int> v;

	for (int i = 0; i < S; ++i)
		inA[X[i]] = true, v.push_back(X[i]);

	for (int i = 0; i < T; ++i)
		inB[Y[i]] = true, v.push_back(Y[i]);

	sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i = 0, k = v.size(); i + 1 < k; ++i)
		v.push_back(lca(v[i], v[i + 1]));

	sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
	v.erase(unique(v.begin(), v.end()), v.end());

	vector<vector<pair<int, ll>>> tree(v.size());
	vector<bool> A(v.size()), B(v.size());

	for (int i = 0; i < v.size(); ++i)
		id[v[i]] = i, A[i] = inA[v[i]], B[i] = inB[v[i]];

	vector<int> stk, nonroot(v.size());

	for (int &x : v)
	{
		while (!stk.empty() && !ancestor(stk.back(), x))
			stk.pop_back();

		if (!stk.empty())
		{
			nonroot[id[x]] = true;
			tree[id[stk.back()]].push_back({id[x], depth[x] - depth[stk.back()]});
		}

		stk.push_back(x);
	}

	assert(count(nonroot.begin(), nonroot.end(), 0) == 1);

	ll ans = oo;

	function<pair<ll, ll>(int, ll)> go = [&](int u, ll d)
	{
		ll a = A[u] ? d : oo;
		ll b = B[u] ? d : oo;

		if (a != oo && b != oo)
			ans = 0;

		for (auto &e : tree[u])
		{
			pair<ll, ll> ch = go(e.first, d + e.second);
			
			ans = min(ans, ch.first + b - 2 * d);
			ans = min(ans, ch.second + a - 2 * d);

			a = min(a, ch.first);
			b = min(b, ch.second);
		}

		return make_pair(a, b);
	};

	go(0, 0);

	for (int i = 0; i < S; ++i)
		inA[X[i]] = false;

	for (int i = 0; i < T; ++i)
		inB[Y[i]] = false;

	return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tour.size(); ++i)
                  ~~^~~~~~~~~~~~~
factories.cpp:61:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + (1 << i) < tour.size(); ++j)
                   ~~~~~~~~~~~~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i)
                  ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1016 KB Output is correct
2 Correct 1063 ms 20028 KB Output is correct
3 Correct 1099 ms 27540 KB Output is correct
4 Correct 1153 ms 37192 KB Output is correct
5 Correct 911 ms 46784 KB Output is correct
6 Correct 604 ms 55972 KB Output is correct
7 Correct 1077 ms 65484 KB Output is correct
8 Correct 1081 ms 75216 KB Output is correct
9 Correct 912 ms 77480 KB Output is correct
10 Correct 617 ms 85764 KB Output is correct
11 Correct 1067 ms 95380 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 95380 KB Output is correct
2 Correct 2082 ms 489500 KB Output is correct
3 Correct 2134 ms 511796 KB Output is correct
4 Runtime error 1635 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1016 KB Output is correct
2 Correct 1063 ms 20028 KB Output is correct
3 Correct 1099 ms 27540 KB Output is correct
4 Correct 1153 ms 37192 KB Output is correct
5 Correct 911 ms 46784 KB Output is correct
6 Correct 604 ms 55972 KB Output is correct
7 Correct 1077 ms 65484 KB Output is correct
8 Correct 1081 ms 75216 KB Output is correct
9 Correct 912 ms 77480 KB Output is correct
10 Correct 617 ms 85764 KB Output is correct
11 Correct 1067 ms 95380 KB Output is correct
12 Correct 6 ms 95380 KB Output is correct
13 Correct 2082 ms 489500 KB Output is correct
14 Correct 2134 ms 511796 KB Output is correct
15 Runtime error 1635 ms 525312 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
16 Halted 0 ms 0 KB -