oj.uz

Submission #385917

# Submission time Handle Problem Language Result Execution time Memory
385917 2021-04-05T08:20:22 Z ogibogi2004 Toll (APIO13_toll) C++14
100 / 100
 2361 ms 22776 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
using namespace std;
#define ll long long
const ll INF=1e15;
const int MAXN=1e5+6;
const int MAXM=3e5+6;
struct edge
{
	ll u,v,w;
	ll idx;
	bool operator<(edge const& other)const
	{
		return w<other.w;
	}
};
ll ans,sum;
ll n,m,k;
bool alwaysin[MAXM];
vector<pair<ll,ll> >g[MAXN];
ll pari[MAXN];
ll pari1[MAXN];
vector<edge>sometimes_in;
edge old[MAXM];
edge nw[20];
vector<ll>comps;
struct DSU
{
	ll par[MAXN],sz[MAXN],h[MAXN];
	void init() 
	{
		for(ll i=1;i<MAXN;i++)
		{
			par[i]=i;sz[i]=1;
			h[i]=pari[i];
		}
	}
	void init(vector<ll>v)
	{
		for(auto xd:v)
		{
			par[xd]=xd;
			sz[xd]=1;
		}
	}
	ll getRoot(ll u)
	{
		if(u==par[u])return u;
		return par[u]=getRoot(par[u]);
	}
	void join(ll p,ll q)
	{
		if(sz[p]>sz[q])
		{
			par[q]=p;
			sz[p]+=sz[q];
			h[p]+=h[q];
		}
		else
		{
			par[p]=q;
			sz[q]+=sz[p];
			h[q]+=h[p];
		}
	}
}dsu1,dsu2;
ll lei[MAXN];
ll atmost[MAXN];
ll par[MAXN];
ll depth[MAXN];
ll subtree[MAXN];
void dfs1(ll u,ll p,ll last_edge_idx=-69)
{
	atmost[u]=INF;
	depth[u]=depth[p]+1;
	subtree[u]=pari1[u];
	lei[u]=last_edge_idx;
	par[u]=p;
	for(auto xd:g[u])
	{
		if(xd.first==p)continue;
		dfs1(xd.first,u,xd.second);
		subtree[u]+=subtree[xd.first];
	}
}
void takovai(edge e)
{
	ll x=e.u,y=e.v;
	if(depth[x]<depth[y])swap(x,y);
	while(depth[x]>depth[y])
	{
		atmost[x]=min(atmost[x],e.w);
		x=par[x];
	}
	while(x!=y)
	{
		atmost[x]=min(atmost[x],e.w);
		atmost[y]=min(atmost[y],e.w);
		x=par[x];y=par[y];
	}
}
void dfs(ll u,ll p)
{
	for(auto xd:g[u])
	{
		if(xd.first==p)continue;
		if(xd.second>m)
		{
			//cout<<"%%%\n";
			sum+=atmost[xd.first]*subtree[xd.first];
		}
		dfs(xd.first,u);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(ll i=1;i<=m;++i)
	{
		cin>>old[i].u>>old[i].v>>old[i].w;
		old[i].idx=i;
	}
	sort(old+1,old+m+1);
	for(ll i=0;i<k;++i)
	{
		cin>>nw[i].u;
		cin>>nw[i].v;
		nw[i].idx=m+i+1;
	}
	for(ll i=1;i<=n;++i)cin>>pari[i];
	dsu1.init();
	for(ll i=0;i<k;++i)
	{
		ll p=dsu1.getRoot(nw[i].u);
		ll q=dsu1.getRoot(nw[i].v);
		if(p!=q)dsu1.join(p,q);
	}
	for(ll i=1;i<=m;++i)
	{
		ll p=dsu1.getRoot(old[i].u);
		ll q=dsu1.getRoot(old[i].v);
		if(p!=q)
		{
			alwaysin[i]=1;
			dsu1.join(p,q);
		}
	}
	dsu1.init();
	for(ll i=1;i<=m;++i)
	{
		ll p=dsu1.getRoot(old[i].u);
		ll q=dsu1.getRoot(old[i].v);
		if(p!=q)
		{
			if(alwaysin[i]!=1)sometimes_in.push_back(old[i]);
			dsu1.join(p,q);
		}
	}
	dsu1.init();
	for(ll i=1;i<=m;++i)
	{
		if(alwaysin[i])
		{
			dsu1.join(dsu1.getRoot(old[i].u),dsu1.getRoot(old[i].v));
		}
	}
	for(ll i=1;i<=n;++i)
	{
		if(dsu1.getRoot(i)==i)comps.push_back(i);
	}
	for(ll i=0;i<k;++i)
	{
		nw[i].u=dsu1.getRoot(nw[i].u);
		nw[i].v=dsu1.getRoot(nw[i].v);
	}
	for(ll i=0;i<sometimes_in.size();++i)
	{
		sometimes_in[i].u=dsu1.getRoot(sometimes_in[i].u);
		sometimes_in[i].v=dsu1.getRoot(sometimes_in[i].v);
	}
	/*for(ll i=1;i<=m;i++)
	{
		if(alwaysin[i])
		{
			cout<<old[i].u<<" "<<old[i].v<<" "<<old[i].w<<endl;
		}
	}*/
	ll root=dsu1.getRoot(1);
	for(ll i=0;i<comps.size();++i)
	{
		pari1[comps[i]]=dsu1.h[comps[i]];
	}
	for(ll mask=1;mask<(1<<k);++mask)
	{
		for(ll i=0;i<comps.size();++i)
		{
			dsu2.par[comps[i]]=comps[i];
			dsu2.sz[comps[i]]=1;
			dsu2.h[comps[i]]=dsu1.h[comps[i]];
		}
		bool ne_stava_brat=0;
		for(ll i=0;i<comps.size();++i)g[comps[i]].clear();
		for(ll i=0;i<k;++i)
		{
			if(mask&(1<<i))
			{
				ll p=dsu2.getRoot(nw[i].u);
				ll q=dsu2.getRoot(nw[i].v);
				if(p==q)
				{
					ne_stava_brat=1;
					break;
				}
				dsu2.join(p,q);
				g[nw[i].u].push_back({nw[i].v,nw[i].idx});
				g[nw[i].v].push_back({nw[i].u,nw[i].idx});
			}
		}
		if(ne_stava_brat)continue;
		vector<edge>ivan;
		for(ll i=0;i<sometimes_in.size();i++)
		{
			ll p=dsu2.getRoot(sometimes_in[i].u);
			ll q=dsu2.getRoot(sometimes_in[i].v);
			if(p==q){ivan.push_back(sometimes_in[i]);continue;}
			dsu2.join(p,q);
			g[sometimes_in[i].u].push_back({sometimes_in[i].v,i});
			g[sometimes_in[i].v].push_back({sometimes_in[i].u,i});
			//ivan.push_back(sometimes_in[i]);
		}
		dfs1(root,0);
		for(auto xd:ivan)takovai(xd);
		sum=0;
		dfs(root,0);
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:180:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |  for(ll i=0;i<sometimes_in.size();++i)
      |             ~^~~~~~~~~~~~~~~~~~~~
toll.cpp:193:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |  for(ll i=0;i<comps.size();++i)
      |             ~^~~~~~~~~~~~~
toll.cpp:199:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |   for(ll i=0;i<comps.size();++i)
      |              ~^~~~~~~~~~~~~
toll.cpp:206:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |   for(ll i=0;i<comps.size();++i)g[comps[i]].clear();
      |              ~^~~~~~~~~~~~~
toll.cpp:225:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |   for(ll i=0;i<sometimes_in.size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 7 ms 5356 KB Output is correct
6 Correct 8 ms 5356 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 7 ms 5356 KB Output is correct
6 Correct 8 ms 5356 KB Output is correct
7 Correct 220 ms 16108 KB Output is correct
8 Correct 221 ms 16108 KB Output is correct
9 Correct 211 ms 16236 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 5 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 7 ms 5356 KB Output is correct
6 Correct 8 ms 5356 KB Output is correct
7 Correct 220 ms 16108 KB Output is correct
8 Correct 221 ms 16108 KB Output is correct
9 Correct 211 ms 16236 KB Output is correct
10 Correct 1766 ms 16364 KB Output is correct
11 Correct 2361 ms 16428 KB Output is correct
12 Correct 2343 ms 22776 KB Output is correct