oj.uz

Submission #707348

# Submission time Handle Problem Language Result Execution time Memory
707348 2023-03-08T20:05:18 Z 600Mihnea Toll (APIO13_toll) C++17
56 / 100
 2500 ms 36060 KB 
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long

struct Info
{
	int a, b, ha, hb;
};

struct Dsu
{
	vector<Info> histo;
	vector<int> t, h;
	int n;
	void init(int nn)
	{
		n = nn;
		t.clear();
		h.clear();
		t.resize(n);
		h.resize(n, 0);
		iota(t.begin(), t.end(), 0);
	}
	int root(int a)
	{
		while (t[a] != a)
		{
			a = t[a];
		}
		return a;
	}
	bool join(int a, int b)
	{
		a = root(a);
		b = root(b);
		histo.push_back({ a, b, h[a], h[b] });
		if (a == b)
		{
			return 0;
		}
		if (h[a] < h[b])
		{
			swap(a, b);
		}
		assert(h[a] >= h[b]);
		t[b] = a;
		h[a] += (h[a] == h[b]);
		return 1;
	}
	void revert()
	{
		assert(!histo.empty());
		Info hi = histo.back();
		histo.pop_back();
		int a = hi.a, b = hi.b, ha = hi.ha, hb = hi.hb;
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		t[a] = a;
		t[b] = b;
		h[a] = ha;
		h[b] = hb;
	}
};


struct Edge
{
	int a;
	int b;
	int cost;
};

bool operator < (Edge fi, Edge sc)
{
	return fi.cost < sc.cost;
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	int n, m, k;
	cin >> n >> m >> k;
	vector<int> people(n);
	vector<Edge> edges, newEdges;
	for (int i = 1; i <= m; i++)
	{
		int a, b, cost;
		cin >> a >> b >> cost;
		a--;
		b--;
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		edges.push_back({ a, b, cost });
	}
	vector<pair<int, int>> spec;
	for (int i = 1; i <= k; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		spec.push_back({ a, b });
	}
	for (auto& p : people)
	{
		cin >> p;
	}
	sort(edges.begin(), edges.end());
	assert((int)edges.size() == m);
	assert((int)spec.size() == k);
	set<pair<int, int>> sspec;

	{
		Dsu dsu;
		dsu.init(n);

		for (auto& edge : edges)
		{
			if (dsu.join(edge.a, edge.b))
			{
				newEdges.push_back(edge);
			}
		}
		edges = newEdges;
	}

	for (int i = 0; i < k; i++)
	{
		int a = spec[i].first, b = spec[i].second;
		sspec.insert({ a, b });
		sspec.insert({ b, a });
	}
	for (auto& edge : edges)
	{
		assert(!sspec.count({ edge.a, edge.b }));
		assert(!sspec.count({ edge.b, edge.a }));
	}
	vector<Edge> mereu, poate;
	{
		Dsu dsu;
		dsu.init(n);
		for (int i = 0; i < k; i++)
		{
			dsu.join(spec[i].first, spec[i].second);
		}
		for (auto& edge : edges)
		{
			if (!dsu.join(edge.a, edge.b))
			{
				poate.push_back(edge);
			}
			else
			{
				mereu.push_back(edge);
			}
		}
	}
	vector<vector<pair<int, int>>> g(n);
	vector<pair<int, int>> now;
	int nredgesinit = 0, nredges = 0;
	auto addedge = [&](int a, int b, int c)
	{
		nredges++;
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		g[a].push_back({ b, c });
		g[b].push_back({ a, c });
		now.push_back({ a, b });
	};
	Dsu dsu;
	dsu.init(n);
	for (auto& edge : mereu)
	{
		bool ok = dsu.join(edge.a, edge.b);
		assert(ok);
		addedge(edge.a, edge.b, edge.cost);
	}
	int szhi = (int)dsu.histo.size();
	nredgesinit = nredges;
	int sol = -1;
	for (int mask = 0; mask < (1 << k); mask++)
	{
		vector<int> inds;
		for (int bit = 0; bit < k; bit++)
		{
			if (mask & (1 << bit))
			{
				inds.push_back(bit);
			}
		}
		nredges = nredgesinit;
		now.clear();
		bool fail = 0;
		for (auto& i : inds)
		{
			if (!dsu.join(spec[i].first, spec[i].second))
			{
				fail = 1;
				break;
			}
			addedge(spec[i].first, spec[i].second, (int)1e9 + 7);
		}
		if (fail)
		{
			for (auto& it : now)
			{
				assert(!g[it.first].empty());
				assert(!g[it.second].empty());
				g[it.first].pop_back();
				g[it.second].pop_back();
			}
			while ((int)dsu.histo.size() > szhi)
			{
				dsu.revert();
			}
			continue;
		}
		vector<Edge> reqs;
		for (auto& edge : poate)
		{
			if (dsu.join(edge.a, edge.b))
			{
				addedge(edge.a, edge.b, edge.cost);
			}
			else
			{
				reqs.push_back(edge);
			}
		}
		vector<int> parof(n), dep(n, 0), valup(n, 0);
		{
			int visited = 0;
			function<void(int, int)> build = [&](int a, int par)
			{
				visited++;
				parof[a] = par;
				for (auto& it : g[a])
				{
					int b = it.first, c = it.second;
					if (b == par)
					{
						continue;
					}
					valup[b] = c;
					dep[b] = 1 + dep[a];
					build(b, a);
				}
			};
			build(0, -1);
			for (auto& req : reqs)
			{
				int a = req.a, b = req.b, cost = req.cost;
				while (a != b)
				{
					if (dep[a] < dep[b])
					{
						swap(a, b);
					}
					assert(dep[a] >= dep[b]);
					if (sspec.count({ parof[a], a }))
					{
						valup[a] = min(valup[a], cost);
					}
					a = parof[a];
				}
			}
		}
		assert(nredges == n - 1);
		vector<int> sub(n, 0);
		int cur = 0;
		function<void(int, int)> build = [&](int a, int par)
		{
			parof[a] = par;
			sub[a] = people[a];
			for (auto& it : g[a])
			{
				int b = it.first;
				if (b == par)
				{
					continue;
				}
				build(b, a);
				sub[a] += sub[b];
				if (sspec.count({ a, b }) || sspec.count({ b, a }))
				{
					cur += sub[b] * valup[b];
				}
			}
		};
		build(0, -1);
		sol = max(sol, cur);
		for (auto& it : now)
		{
			assert(!g[it.first].empty());
			assert(!g[it.second].empty());
			g[it.first].pop_back();
			g[it.second].pop_back();
			dsu.revert();
		}
		while ((int)dsu.histo.size() > szhi)
		{
			dsu.revert();
		}
	}
	cout << sol << "\n";
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 118 ms 788 KB Output is correct
6 Correct 58 ms 788 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 118 ms 788 KB Output is correct
6 Correct 58 ms 788 KB Output is correct
7 Execution timed out 2551 ms 36060 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 118 ms 788 KB Output is correct
6 Correct 58 ms 788 KB Output is correct
7 Execution timed out 2551 ms 36060 KB Time limit exceeded
8 Halted 0 ms 0 KB -