oj.uz

Submission #50682

# Submission time Handle Problem Language Result Execution time Memory
50682 2018-06-12T14:18:09 Z ayhcbagnop Toll (APIO13_toll) C++14
100 / 100
 2239 ms 46700 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 528 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 900 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 900 KB Output is correct
7 Correct 253 ms 14144 KB Output is correct
8 Correct 265 ms 20616 KB Output is correct
9 Correct 296 ms 27112 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 900 KB Output is correct
7 Correct 253 ms 14144 KB Output is correct
8 Correct 265 ms 20616 KB Output is correct
9 Correct 296 ms 27112 KB Output is correct
10 Correct 1823 ms 33616 KB Output is correct
11 Correct 2239 ms 40068 KB Output is correct
12 Correct 2065 ms 46700 KB Output is correct