Submission #991742

#	Time	Username	Problem	Language	Result	Execution time	Memory
991742		vjudge1	Toll (APIO13_toll)	C++17	0 / 100	2 ms	12120 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5 + 1, lg = 17;

vector<int> ver[M];
set<int> nei[M];
int dep[M],par[M][lg],col[M],sz[M],a[M],subt[M];

void add(int u,int v)
{
	int x=col[u],y=col[v];
	if (sz[x]<sz[y])
	{
		swap(u,v);
		swap(x,y);
	}
	for (int i:ver[y])
	{
		col[i]=x;
		ver[x].push_back(i);
		sz[x]++;
	}
	ver[y].clear();
	sz[y]=0;
}

void dfs(int u,int p=0)
{
	par[u][0]=p;
	for (int i=1;i<lg;i++)
		par[u][i]=par[par[u][i-1]][i-1];
	subt[u]=a[u];
	for (int i:nei[u])
		if (i!=p)
		{
			dep[i]=dep[u]+1;
			dfs(i,u);
			subt[u]+=subt[i];
		}
}

bool pr(int u,int v)
{
	if (dep[v]<dep[u])
		return false;
	int d=dep[v]-dep[u];
	for (int i=0;i<lg;i++)
		if ((1<<i)&d)
			v=par[v][i];
	return u==v;
}

bool rep(int u,int v,int x,int y)
{
	if (par[v][0]!=u)
		swap(u,v);
	return (pr(v,x)^pr(v,y));
}

signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<pair<int,pair<int,int>>> ed;
	set<pair<int,pair<int,int>>,greater<pair<int,pair<int,int>>>> se,nw; 
	for (int i=1;i<=n;i++)
	{
		col[i]=i;
		sz[i]=1;
		ver[i]={i};
	}
	for (int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		ed.push_back({w,{u,v}});
	}
	for (auto i:ed)
	{
		int w=i.first,u=i.second.first,v=i.second.second;
		if (col[u]!=col[v])
		{
			add(u,v);
			se.insert({w,{u,v}});
		}
	}
	for (auto i:se)
	{
		nei[i.second.first].insert(i.second.second);
		nei[i.second.second].insert(i.second.first);
	}
	dfs(1);
	for (int j=0;j<k;j++)
	{
		int x,y;
		cin>>x>>y;
		for (auto i:se)
		{
			int u=i.second.first,v=i.second.second;
			if (rep(u,v,x,y))
			{
				nei[u].erase(v);
				nei[v].erase(u);
				nei[x].insert(y);
				nei[y].insert(x);
				nw.insert({i.first,{x,y}});
				se.erase(i);
				break;
			}
		}
		dfs(1);
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1);
	for (auto i:nw)
	{
		int w=i.first,u=i.second.first,v=i.second.second;
		if (par[v][0]!=u)
			swap(u,v);
		ans+=w*subt[v];
	}
	cout<<ans<<endl;
	
	return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22