oj.uz

Submission #725100

# Submission time Handle Problem Language Result Execution time Memory
725100 2023-04-16T22:44:12 Z faremy Road Closures (APIO21_roads) C++17
5 / 100
 341 ms 38824 KB 
#include <iostream>
#include <random>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

//Wrapper for generating random integers from [0, N[
class RandInt
{
        static std::random_device rd;
        static std::mt19937 gen;
        std::uniform_int_distribution<ll> distrib;

public:
        RandInt(ll N) : distrib(0, N - 1) {}
        ll operator ()() { return distrib(gen); }
};

std::random_device RandInt::rd;
std::mt19937 RandInt::gen(rd());

//End of template

#include "roads.h"

#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
#include <algorithm>

//Treap
struct TreapNode
{
	TreapNode(ll v) : value(v), priority(gen_prio()), sum(v) {}
	~TreapNode() { delete left; delete right; }

	ll value, priority;
	int size = 1;
	ll sum;
	TreapNode *left = nullptr, *right = nullptr;

private:
	static RandInt gen_prio;
};

const ll INFTY = 1LL << 62;
RandInt TreapNode::gen_prio(INFTY);

using Treap = TreapNode *;
using Treapair = std::pair<Treap, Treap>;

int size(Treap t)
{
	if (t)
		return t->size;
	return 0;
}

ll sum(Treap t)
{
	if (t)
		return t->sum;
	return 0;
}

Treapair cut(Treap t, ll v)
{
	if (t == nullptr)
		return { nullptr, nullptr };
	if (t->value < v)
	{
		Treapair sub = cut(t->right, v);
		t->right = sub.first;
		t->size -= size(sub.second);
		t->sum -= sum(sub.second);
		return { t, sub.second };
	}
	else
	{
		Treapair sub = cut(t->left, v);
		t->left = sub.second;
		t->size -= size(sub.first);
		t->sum -= sum(sub.first);
		return { sub.first, t };
	}
}

Treap merge(Treap l, Treap r)
{
	if (l == nullptr)
		return r;
	if (r == nullptr)
		return l;
	if (l->priority > r->priority)
	{
		l->size += size(r);
		l->sum += sum(r);
		l->right = merge(l->right, r);
		return l;
	}
	else
	{
		r->size += size(l);
		r->sum += sum(l);
		r->left = merge(l, r->left);
		return r;
	}
}

void insert(Treap &t, ll v)
{
	Treapair split = cut(t, v);
	t = merge(merge(split.first, new TreapNode(v)), split.second);
}

int cnt_range(Treap &t, ll a, ll b)
{
	Treapair low = cut(t, a);
	Treapair high = cut(low.second, b);
	int res = size(high.first);
	t = merge(low.first, merge(high.first, high.second));
	return res;
}

ll sum_k(Treap &t, int k)
{
	if (k == 0)
		return 0;
	if (t == nullptr)
		return INFTY;
	
	if (k > size(t->left))
		return sum(t->left) + t->value + sum_k(t->right, k - size(t->left) - 1);
	return sum_k(t->left, k);
}

ll sum_k_range(Treap &t, ll a, ll b, int k)
{
	Treapair low = cut(t, a);
	Treapair high = cut(low.second, b);
	ll res = sum_k(high.first, k);
	t = merge(low.first, merge(high.first, high.second));
	return res;
}

//Main code
const int MAXN = 1e5;

std::unordered_map<int, ll> tree[MAXN];
Treap dead_neighbors[MAXN];
int degree[MAXN];
int deg_order[MAXN];

bool seen[MAXN];
ll min_cuts[MAXN][2];

ll cut_children(int node, int parent, int maxdeg)
{
	int remain = degree[node] - maxdeg;
	std::priority_queue<ll> add_cost;
	ll res = 0;

	for (auto [child, _] : tree[node])
	{
		if (child != parent)
		{
			if (min_cuts[child][1] > min_cuts[child][0])
			{
				res += min_cuts[child][0];
				add_cost.emplace(min_cuts[child][0] - min_cuts[child][1]);
			}
			else
			{
				res += min_cuts[child][1];
				remain--;
			}
		}
	}

	ll previous_alive = 0;
	while (remain > 0 && !add_cost.empty())
	{
		ll smallest_alive = -add_cost.top();
		add_cost.pop();

		int cnt_dead = cnt_range(dead_neighbors[node], previous_alive, smallest_alive);
		if (cnt_dead < remain)
		{
			res += sum_k_range(dead_neighbors[node], previous_alive, smallest_alive, cnt_dead) + smallest_alive;
			remain -= cnt_dead + 1;
		}
		else
		{
			res += sum_k_range(dead_neighbors[node], previous_alive, smallest_alive, remain);
			remain = 0;
		}

		previous_alive = smallest_alive;
	}

	res += sum_k_range(dead_neighbors[node], previous_alive, INFTY, remain);
	return res;
}

void compute_cuts(int node, int parent, int maxdeg)
{
	seen[node] = true;
	for (auto [child, _] : tree[node])
		if (child != parent)
			compute_cuts(child, node, maxdeg);

	min_cuts[node][0] = cut_children(node, parent, maxdeg);
	if (parent != -1)
		min_cuts[node][1] = cut_children(node, parent, maxdeg + 1) + tree[node][parent];
}

std::vector<ll> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	for (int iEdge = 0; iEdge < N - 1; iEdge++)
	{
		tree[U[iEdge]][V[iEdge]] = W[iEdge];
		tree[V[iEdge]][U[iEdge]] = W[iEdge];
	}
	
	for (int iNode = 0; iNode < N; iNode++)
	{
		dead_neighbors[iNode] = nullptr;
		degree[iNode] = tree[iNode].size();
		deg_order[iNode] = iNode;
		seen[iNode] = false;
	}

	std::sort(deg_order, deg_order + N, [](int u, int v) { return degree[u] < degree[v]; });
	int first_alive = 0;

	std::vector<ll> ans(N, 0);
	for (int maxdeg = 0; maxdeg < N; maxdeg++)
	{
		while (first_alive < N && degree[deg_order[first_alive]] <= maxdeg)
		{
			for (auto [neighbor, weight] : tree[deg_order[first_alive]])
			{
				tree[neighbor].erase(tree[neighbor].find(deg_order[first_alive]));
				insert(dead_neighbors[neighbor], weight);
			}
			first_alive++;
		}

		for (int iNode = first_alive; iNode < N; iNode++)
			if (!seen[deg_order[iNode]])
			{
				compute_cuts(deg_order[iNode], -1, maxdeg);
				ans[maxdeg] += min_cuts[deg_order[iNode]][0];
			}

		for (int iNode = first_alive; iNode < N; iNode++)
			seen[deg_order[iNode]] = false;
	}

	for (int iNode = 0; iNode < N; iNode++)
		delete dead_neighbors[iNode];
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 6 ms 6356 KB Output is correct
3 Correct 9 ms 6484 KB Output is correct
4 Correct 7 ms 6484 KB Output is correct
5 Correct 4 ms 5788 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 6 ms 6316 KB Output is correct
9 Correct 6 ms 6348 KB Output is correct
10 Correct 4 ms 5844 KB Output is correct
11 Correct 6 ms 5796 KB Output is correct
12 Correct 139 ms 25008 KB Output is correct
13 Correct 236 ms 37972 KB Output is correct
14 Correct 243 ms 35440 KB Output is correct
15 Correct 341 ms 38344 KB Output is correct
16 Correct 274 ms 38824 KB Output is correct
17 Correct 223 ms 38756 KB Output is correct
18 Correct 4 ms 5716 KB Output is correct
19 Correct 192 ms 35028 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Incorrect 95 ms 37524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 4 ms 5796 KB Output is correct
4 Incorrect 4 ms 5844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 4 ms 5796 KB Output is correct
4 Incorrect 4 ms 5844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 6 ms 6356 KB Output is correct
3 Correct 9 ms 6484 KB Output is correct
4 Correct 7 ms 6484 KB Output is correct
5 Correct 4 ms 5788 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5844 KB Output is correct
8 Correct 6 ms 6316 KB Output is correct
9 Correct 6 ms 6348 KB Output is correct
10 Correct 4 ms 5844 KB Output is correct
11 Correct 6 ms 5796 KB Output is correct
12 Correct 139 ms 25008 KB Output is correct
13 Correct 236 ms 37972 KB Output is correct
14 Correct 243 ms 35440 KB Output is correct
15 Correct 341 ms 38344 KB Output is correct
16 Correct 274 ms 38824 KB Output is correct
17 Correct 223 ms 38756 KB Output is correct
18 Correct 4 ms 5716 KB Output is correct
19 Correct 192 ms 35028 KB Output is correct
20 Correct 4 ms 5716 KB Output is correct
21 Incorrect 95 ms 37524 KB Output isn't correct
22 Halted 0 ms 0 KB -