Submission #115621

#	Time	Username	Problem	Language	Result	Execution time	Memory
115621		Mahdi_Jfri	Toll (APIO13_toll)	C++14	100 / 100	1735 ms	21408 KiB

toll

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
 
const int maxn = 3e5 + 200;

int from[maxn] , to[maxn] , w[maxn] , ind[maxn];

int par[maxn];
ll p[maxn] , sub[maxn];

bool mst[maxn] , in_all[maxn];

vector<int> adj[maxn];

int fn(int v)
{
	return par[v] < 0? v : par[v] = fn(par[v]);
}

bool cn(int a , int b)
{
	a = fn(a) , b = fn(b);
	return a == b;
}

void merge(int a , int b)
{
	a = fn(a) , b = fn(b);
	if(a != b)
		par[b] = a;
}

bool cmp(int a , int b)
{
	return w[a] < w[b];
}

int dad[maxn] , h[maxn];

void dfs(int v , int px = -1)
{
	sub[v] = p[v];
	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;
		if(u != px)
		{
			dad[u] = e;
			h[u] = h[v] + 1;
			dfs(u , v);
			sub[v] += sub[u];
		}
	}
}

void reval(int &v , int val)
{
	w[dad[v]] = min(w[dad[v]] , val);
	v = from[dad[v]] ^ to[dad[v]] ^ v;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	memset(par , -1 , sizeof par);

	int n , m , k;
	cin >> n >> m >> k;

	for(int i = 0; i < m + k; i++)
	{
		int a , b;
		cin >> a >> b;
		if(i < m)
			cin >> w[i];

		a-- , b--;
		from[i] = a , to[i] = b;
		ind[i] = i;
	}

	sort(ind , ind + m , cmp);

	for(int i = 0; i < n; i++)
		cin >> p[i];
	
	for(int i = 0; i < m; i++)
	{
		int k = ind[i];
		mst[k] = !cn(from[k] , to[k]);
		merge(from[k] , to[k]);
	}

	memset(par , -1 , sizeof par);

	for(int i = m; i < m + k; i++)
		merge(from[i] , to[i]);

	for(int i = 0; i < m; i++)
	{
		int k = ind[i];
		in_all[k] = !cn(from[k] , to[k]);
		merge(from[k] , to[k]);
	}

	memset(par , -1 , sizeof par);

	for(int i = 0; i < m; i++)
		if(in_all[i])
			merge(from[i] , to[i]);

	vector<int> nodes;
	for(int i = 0; i < n; i++)
	{
		if(par[i] < 0)
			nodes.pb(i);
		else
			p[fn(i)] += p[i];
	}

	for(int i = 0; i < m + k; i++)
		from[i] = fn(from[i]) , to[i] = fn(to[i]);

	vector<int> imp;
	for(int i = 0; i < m; i++)
		if(!in_all[ind[i]] && mst[ind[i]])
			imp.pb(ind[i]);

	ll res = 0;

	int root = fn(0);
	for(int mask = 1; mask < (1 << k); mask++)
	{
		for(auto v : nodes)
			adj[v].clear() , par[v] = -1;

		bool f = 1;
		for(int i = m; i < m + k; i++)
		{
			w[i] = 2e9;
			if(bit(mask , i - m))
			{
				f &= !cn(from[i] , to[i]);
				merge(from[i] , to[i]);
				adj[from[i]].pb(i);
				adj[to[i]].pb(i);
			}
		}

		if(!f)
			break;

		for(auto ind : imp)
			if(!cn(from[ind] , to[ind]))
			{
				merge(from[ind] , to[ind]);
				adj[from[ind]].pb(ind);
				adj[to[ind]].pb(ind);
			}

		dfs(root);

		for(auto ind : imp)
		{
			int v = from[ind] , u = to[ind];
			if(h[v] < h[u])
				swap(v , u);
			while(h[v] > h[u])
				reval(v , w[ind]);
			while(v != u)
			{
				reval(v , w[ind]);
				reval(u , w[ind]);
			}
		}

		ll sum = 0;
		for(auto v : nodes)
			if(dad[v] >= m)
				sum += w[dad[v]] * sub[v];

		res = max(res , sum);
	}

	cout << res << endl;
}

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22