oj.uz

Submission #115621

# Submission time Handle Problem Language Result Execution time Memory
115621 2019-06-08T11:19:24 Z Mahdi_Jfri Toll (APIO13_toll) C++14
100 / 100
 1735 ms 21408 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
4 Correct 9 ms 8576 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
4 Correct 9 ms 8576 KB Output is correct
5 Correct 11 ms 8832 KB Output is correct
6 Correct 12 ms 8832 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
4 Correct 9 ms 8576 KB Output is correct
5 Correct 11 ms 8832 KB Output is correct
6 Correct 12 ms 8832 KB Output is correct
7 Correct 235 ms 21276 KB Output is correct
8 Correct 230 ms 21408 KB Output is correct
9 Correct 227 ms 21244 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
4 Correct 9 ms 8576 KB Output is correct
5 Correct 11 ms 8832 KB Output is correct
6 Correct 12 ms 8832 KB Output is correct
7 Correct 235 ms 21276 KB Output is correct
8 Correct 230 ms 21408 KB Output is correct
9 Correct 227 ms 21244 KB Output is correct
10 Correct 1198 ms 21388 KB Output is correct
11 Correct 1672 ms 21372 KB Output is correct
12 Correct 1735 ms 21340 KB Output is correct