oj.uz

답안 #708923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708923 2023-03-12T17:34:47 Z 600Mihnea 통행료 (APIO13_toll) C++17
78 / 100
 2500 ms 30036 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 <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long

struct Dsu
{
	vector<int> t, wha;
	bool spec;
	int n;
	void init(int nn)
	{
		spec = 0;
		wha.clear();
		n = nn;
		t.clear();
		t.resize(n);
		iota(t.begin(), t.end(), 0);
	}
	int root(int a)
	{
		if (!spec)
		{
			if (t[a] == a)
			{
				return a;
			}
			return t[a] = root(t[a]);
		}
		return wha[a];
	}

	bool join(int a, int b)
	{
		a = root(a);
		b = root(b);
		if (a == b)
		{
			return 0;
		}
		t[b] = a;
		return 1;
	}
	int nrml()
	{
		wha.resize(n);
		map<int, int> mp;
		mp.clear();
		for (int i = 0; i < n; i++)
		{
			mp[root(i)] = 0;
		}
		int y = 0;
		for (auto& it : mp)
		{
			it.second = y++;
		}
		for (int i = 0; i < n; i++)
		{
			wha[i] = mp[root(i)];
		}
		spec = 1;
		return y;
	}
};

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

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


vector<int> parof, dep, valup, isspec, sub;
vector<vector<pair<int, int>>> g;
int cur;
vector<int> su;

void build2(int a, int par)
{
	parof[a] = par;
	for (auto& it : g[a])
	{
		int b = it.first, c = it.second;
		if (b == par)
		{
			continue;
		}
		isspec[b] = (c == (int)1e9 + 7);

		valup[b] = c;
		dep[b] = 1 + dep[a];
		build2(b, a);
	}
};

void build(int a, int par)
{
	parof[a] = par;
	sub[a] = su[a];
	for (auto& it : g[a])
	{
		int b = it.first;
		if (b == par)
		{
			continue;
		}
		build(b, a);
		sub[a] += sub[b];
		cur += isspec[b] * sub[b] * valup[b];
	}
};

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--;
		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--;
		spec.push_back({ a, b });
	}
	for (auto& p : people)
	{
		cin >> p;
	}
	sort(edges.begin(), edges.end());
	{
		Dsu dsu;
		dsu.init(n);

		for (auto& edge : edges)
		{
			if (dsu.join(edge.a, edge.b))
			{
				newEdges.push_back(edge);
			}
		}
		edges = newEdges;
	}
	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);
			}
		}
	}
	g.resize(n);
	int nredgesinit = 0, nredges = 0;
	auto addedge = [&](int a, int b, int c)
	{
		nredges++;
		g[a].push_back({ b, c });
		g[b].push_back({ a, c });
	};
	Dsu dsuinit;
	dsuinit.init(n);
	for (auto& edge : mereu)
	{
		dsuinit.join(edge.a, edge.b);
		addedge(edge.a, edge.b, edge.cost);
	}
	int y = dsuinit.nrml();
	for (auto& edge : poate)
	{
		edge.a = dsuinit.root(edge.a);
		edge.b = dsuinit.root(edge.b);
	}
	nredgesinit = nredges;
	su.resize(y, 0);
	for (int i = 0; i < n; i++)
	{
		su[dsuinit.root(i)] += people[i];
	}
	for (int i = 0; i < n; i++)
	{
		g[i].clear();
	}
	Dsu dsu;
	dsu.init(y);
	parof.resize(y), dep.resize(y, 0), valup.resize(y, 0), isspec.resize(y, 0), sub.resize(y);
	int dim = (int)poate.size();
	vector<int> mnbit(1 << dim);
	for (int i = 0; i < (1 << dim); i++)
	{
		for (int j = 0; j < dim; j++)
		{
			if (i & (1 << j))
			{
				mnbit[i] = j;
				break;
			}
		}
	}
	vector<int> inds, inds_reqs;
	int sol = -1;
	for (int mask = 0; mask < (1 << k); mask++)
	{
		inds.clear();
		for (int i = 0; i < y; i++)
		{
			dsu.t[i] = i;
		}
		for (int bit = 0; bit < k; bit++)
		{
			if (mask & (1 << bit))
			{
				inds.push_back(bit);
			}
		}
		nredges = nredgesinit;
		bool fail = 0;
		g.clear();
		g.resize(y);
		for (auto& i : inds)
		{
			if (!dsu.join(dsuinit.root(spec[i].first), dsuinit.root(spec[i].second)))
			{
				fail = 1;
				break;
			}
			addedge(dsuinit.root(spec[i].first), dsuinit.root(spec[i].second), (int)1e9 + 7);
		}
		if (fail)
		{
			continue;
		}
		inds_reqs.clear();
		int yandex = 0;
		for (auto& edge : poate)
		{
			if (dsu.join(edge.a, edge.b))
			{
				addedge(edge.a, edge.b, edge.cost);
			}
			else
			{
				inds_reqs.push_back(yandex);
			}
			yandex++;
		}
		for (int i = 0; i < y; i++)
		{
			isspec[i] = 0;
		}
		{
			build2(dsuinit.root(0), -1);
			vector<int> who(n, 0);
			for (auto& i : inds_reqs)
			{
				int a = poate[i].a, b = poate[i].b, cost = poate[i].cost;
				if (a == b) continue;
				who[a] += (1 << i);
				who[b] += (1 << i);
			}
			function<void(int,int)> gather = [&](int a, int par)
			{
				for (auto& it : g[a])
				{
					int b = it.first, c = it.second;
					if (b == par)
					{
						continue;
					}
					gather(b, a);
					who[a] ^= who[b];
				}
				if (who[a])
				{
					valup[a] = min(valup[a], poate[mnbit[who[a]]].cost);
				}
			};
			gather(dsuinit.root(0), -1);
		}
		cur = 0;
		build(dsuinit.root(0), -1);
		sol = max(sol, cur);
	}
	cout << sol << "\n";
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:314:41: warning: unused variable 'cost' [-Wunused-variable]
  314 |     int a = poate[i].a, b = poate[i].b, cost = poate[i].cost;
      |                                         ^~~~
toll.cpp: In lambda function:
toll.cpp:323:24: warning: unused variable 'c' [-Wunused-variable]
  323 |      int b = it.first, c = it.second;
      |                        ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 866 ms 22796 KB Output is correct
8 Correct 860 ms 22876 KB Output is correct
9 Correct 835 ms 22056 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 866 ms 22796 KB Output is correct
8 Correct 860 ms 22876 KB Output is correct
9 Correct 835 ms 22056 KB Output is correct
10 Execution timed out 2569 ms 30036 KB Time limit exceeded
11 Halted 0 ms 0 KB -