Submission #114682

#	Time	Username	Problem	Language	Result	Execution time	Memory
114682		WhipppedCream	Toll (APIO13_toll)	C++14	100 / 100	1677 ms	14080 KiB

toll

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef long long ll;
const int maxn = 1e5+5;
const int maxk = 25;
struct edge
{
	int u, v, w;
	bool is_hard, in_mst;
	edge(int _u, int _v, int _w)
	{
		u = _u; v = _v; w = _w;
		is_hard = 0;
		in_mst = 0;
	}
	bool operator < (edge other)
	{
		return w< other.w;
	}
};
int n, m, k;
int size;
int par[maxn];
int sz[maxn];
int treecomp[maxn];
ll treesz[maxn];
vi adj[maxk];
vi weight[maxk];
int dep[maxk];
int up[maxk];
ll subsz[maxk];
int b4[maxk];
void setsz(int x)
{
	size = x;
} 
void reset()
{
	for(int i = 1; i<= size; i++) par[i] = i;
}
int pong(int x)
{
	if(par[x] == x) return x;
	return par[x] = pong(par[x]);
}
void tfs(int u, int par)
{
	subsz[u] = treesz[u];
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i], w = weight[u][i];
		if(v == par) continue;
		up[v] = w;
		dep[v] = dep[u]+1;
		b4[v] = u;
		tfs(v, u);
		subsz[u] += subsz[v];
	}
}
int main()
{
	scanf("%d %d %d", &n, &m, &k);
	vector<edge> norm;
	vector<edge> sp;
	for(int i = 0; i< m; i++)
	{
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		norm.pb(edge(u, v, w));
	}
	for(int i = 0; i< k; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		sp.pb(edge(u, v, 0));
	}
	for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
	sort(norm.begin(), norm.end());
	setsz(n);
	reset();
	for(int i = 0; i< m; i++)
	{
		int a = pong(norm[i].u), b = pong(norm[i].v);
		if(a == b) continue;
		par[a] = b; norm[i].in_mst = true;
		//printf("%d %d is in mst\n", norm[i].u, norm[i].v);
	}
	reset();
	for(int i = 0; i< k; i++)
	{
		int a = pong(sp[i].u), b = pong(sp[i].v);
		//printf("connect %d %d\n", a, b);
		par[a] = b;
	}
	for(int i = 0; i< m; i++)
	{
		int a = pong(norm[i].u), b = pong(norm[i].v);
		if(a == b) continue;
		par[a] = b;
		//printf("%d %d is hard!\n", norm[i].u, norm[i].v);
		norm[i].is_hard = true;
	}
	reset();
	vector<edge> soft;
	for(int i = 0; i< m; i++)
	{
		if(norm[i].is_hard)
		{
			int a = pong(norm[i].u), b = pong(norm[i].v);
			par[a] = b;
		}
	}
	int comps = 0;
	for(int i = 1; i<= n; i++)
	{
		if(pong(i) == i)
		{
			comps++; treecomp[i] = comps; 
		}
	}
	for(int i = 1; i<= n; i++)
	{
		if(pong(i) != i)
		{
			treecomp[i] = treecomp[pong(i)];
		}
	}
	for(int i = 1; i<= n; i++) treesz[treecomp[pong(i)]] += sz[i];
	for(int i = 0; i< m; i++)
	{
		if(!norm[i].is_hard && norm[i].in_mst)
		{
			soft.pb(edge(treecomp[norm[i].u], treecomp[norm[i].v], norm[i].w));
		}
	}
	ll best = 0;
	for(int mask = 0; mask < (1<<k); mask++)
	{
		setsz(comps); reset();
		bool is_cycle = false;
		for(int i = 1; i<= comps; i++)
		{
			adj[i].clear(); weight[i].clear();
		}
		for(int i = 0; i< k; i++)
		{
			if((1<<i)&mask)
			{
				int a = pong(treecomp[sp[i].u]), b = pong(treecomp[sp[i].v]);
				if(a == b)
				{
					is_cycle = true;
					break;
				}
				par[a] = b;
				adj[treecomp[sp[i].u]].pb(treecomp[sp[i].v]); weight[treecomp[sp[i].u]].pb(2e9);
				adj[treecomp[sp[i].v]].pb(treecomp[sp[i].u]); weight[treecomp[sp[i].v]].pb(2e9);
			}
		}
		if(is_cycle) continue;
		vector<edge> gas;
		for(int i = 0; i< (int) soft.size(); i++)
		{
			int a = pong(soft[i].u), b = pong(soft[i].v);
			if(a == b) gas.pb(soft[i]);
			else
			{
				par[a] = b;
				adj[soft[i].u].pb(soft[i].v); weight[soft[i].u].pb(0);
				adj[soft[i].v].pb(soft[i].u); weight[soft[i].v].pb(0);
			}
		}
		dep[treecomp[1]] = 1; tfs(treecomp[1], 0);
		for(int i = 0; i< (int) gas.size(); i++)
		{
			int u = gas[i].u, v = gas[i].v;
			int w = gas[i].w;
			if(dep[u]< dep[v]) swap(u, v);
			while(dep[u]> dep[v])
			{
				up[u] = min(up[u], w);
				u = b4[u];
			}
			while(u != v)
			{
				up[u] = min(up[u], w);
				up[v] = min(up[v], w);
				u = b4[u], v = b4[v];
			}
		}
		ll here = 0;
		for(int i = 1; i<= comps; i++) if(treecomp[1] != i) here += 1LL*subsz[i]*up[i];
		best = max(here, best);
	}
	printf("%lld\n", best);
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:69:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:77:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
                             ~~~~~^~~~~~~~~~~~~~

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