oj.uz

Submission #114682

# Submission time Handle Problem Language Result Execution time Memory
114682 2019-06-02T09:51:47 Z WhipppedCream Toll (APIO13_toll) C++14
100 / 100
 1677 ms 14080 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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 5 ms 640 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 213 ms 13976 KB Output is correct
8 Correct 227 ms 13916 KB Output is correct
9 Correct 225 ms 13888 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 213 ms 13976 KB Output is correct
8 Correct 227 ms 13916 KB Output is correct
9 Correct 225 ms 13888 KB Output is correct
10 Correct 1494 ms 13888 KB Output is correct
11 Correct 1677 ms 14080 KB Output is correct
12 Correct 1644 ms 13916 KB Output is correct