oj.uz

Submission #385529

# Submission time Handle Problem Language Result Execution time Memory
385529 2021-04-04T14:29:41 Z ogibogi2004 Toll (APIO13_toll) C++14
56 / 100
 862 ms 22140 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e16;
ll n,m,k;
struct edge
{
	ll u,v,w;
	bool operator<(edge const& other)const
	{
		return w<other.w;
	}
};
ll ans,sum;
vector<edge>e;
vector<edge>nmst;
vector<edge>mst;
ll st[20],en[20];
vector<pair<ll,ll> >g[1024];
ll par[1024],sz[1024];
ll dp1[1024][12];
ll depth[1024];
ll h[1024];
vector<ll>spec[1024][12];
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];
	}
	else
	{
		par[p]=q;
		sz[q]+=sz[p];
	}
}
void dfs(ll u,ll p,ll s)
{
	dp1[u][0]=p;
	depth[u]=depth[p]+1;
	if(s>=0)spec[u][0].push_back(s);
	for(auto xd:g[u])
	{
		if(xd.first==p)continue;
		if(xd.second>0)dfs(xd.first,u,-1);
		else dfs(xd.first,u,-xd.second);
	}
}
void precompute()
{
	for(ll step=0;step<10;step++)
	{
		for(ll i=1;i<=n;i++)
		{
			spec[i][step+1]=spec[i][step];
			for(auto xd:spec[dp1[i][step]][step])
			{
				spec[i][step+1].push_back(xd);
			}
			dp1[i][step+1]=dp1[dp1[i][step]][step];
		}
	}
}
vector<ll> on_path(ll x,ll y)
{
	if(depth[x]<depth[y])swap(x,y);
	ll diff=depth[x]-depth[y];
	vector<ll>ret;
	for(ll i=0;i<12;i++)
	{
		if(diff&(1<<i))
		{
			for(auto xd:spec[x][i])
			{
				ret.push_back(xd);
			}
			x=dp1[x][i];
		}
	}
	if(x==y)return ret;
	for(ll i=11;i>=0;i--)
	{
		if(dp1[x][i]!=dp1[y][i])
		{
			for(auto xd:spec[x][i])
			{
				ret.push_back(xd);
			}
			for(auto xd:spec[y][i])
			{
				ret.push_back(xd);
			}
			x=dp1[x][i];
			y=dp1[y][i];
		}
	}
	for(auto xd:spec[x][0])ret.push_back(xd);
	for(auto xd:spec[y][0])ret.push_back(xd);
	return ret;
}
ll res[22];
ll sbt[1024];
void dfs1(ll u,ll p)
{
	sbt[u]=h[u];
	for(auto xd:g[u])
	{
		if(xd.first==p)continue;
		dfs1(xd.first,u);
		if(xd.second<=0)
		{
			sum+=sbt[xd.first]*res[-xd.second];
		}
		sbt[u]+=sbt[xd.first];
	}
}
void check(ll mask)
{
	for(ll i=1;i<=n;i++)
	{
		g[i].clear();
		par[i]=i;sz[i]=1;
		for(ll j=0;j<12;j++)spec[i][j].clear();
	}
	mst.clear();
	nmst.clear();
	for(ll i=0;i<k;i++)
	{
		if(mask&(1<<i))
		{
			ll p=getRoot(st[i]);
			ll q=getRoot(en[i]);
			if(p==q)return;
			join(p,q);
			mst.push_back({st[i],en[i],-i});
		}
	}
	for(auto ed:e)
	{
		ll p=getRoot(ed.u);
		ll q=getRoot(ed.v);
		if(p==q)
		{
			nmst.push_back(ed);
			continue;
		}
		join(p,q);
		mst.push_back(ed);
	}
	for(ll i=0;i<mst.size();i++)
	{
		g[mst[i].u].push_back({mst[i].v,mst[i].w});
		g[mst[i].v].push_back({mst[i].u,mst[i].w});
	}
	dfs(1,0,0);
	precompute();
	for(ll i=0;i<=k;i++)res[i]=INF;
	for(auto xd:nmst)
	{
		vector<ll>v=on_path(xd.u,xd.v);
		for(auto dx:v)
		{
			res[dx]=min(res[dx],xd.w);
		}
	}
	for(ll i=0;i<1024;i++)sbt[i]=0;
	sum=0;
	dfs1(1,0);
	ans=max(ans,sum);
}
int main()
{
	cin>>n>>m>>k;
	for(ll i=1;i<=m;i++)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		e.push_back({x,y,z});
	}
	sort(e.begin(),e.end());
	for(ll i=0;i<k;i++)
	{
		cin>>st[i]>>en[i];
	}
	for(ll i=1;i<=n;i++)cin>>h[i];
	for(ll mask=0;mask<(1<<k);mask++)
	{
		check(mask);
	}
	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 'void check(long long int)':
toll.cpp:156:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |  for(ll i=0;i<mst.size();i++)
      |             ~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 18 ms 748 KB Output is correct
4 Correct 13 ms 748 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 18 ms 748 KB Output is correct
4 Correct 13 ms 748 KB Output is correct
5 Correct 862 ms 1452 KB Output is correct
6 Correct 534 ms 1684 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 18 ms 748 KB Output is correct
4 Correct 13 ms 748 KB Output is correct
5 Correct 862 ms 1452 KB Output is correct
6 Correct 534 ms 1684 KB Output is correct
7 Runtime error 364 ms 22140 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 18 ms 748 KB Output is correct
4 Correct 13 ms 748 KB Output is correct
5 Correct 862 ms 1452 KB Output is correct
6 Correct 534 ms 1684 KB Output is correct
7 Runtime error 364 ms 22140 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -