Submission #257479

#	Time	Username	Problem	Language	Result	Execution time	Memory
257479		davooddkareshki	Toll (APIO13_toll)	C++17	16 / 100	128 ms	163844 KiB

toll

#include<bits/stdc++.h>

using namespace std;
 
#define int long long
#define F first 
#define S second 
#define pii pair<int,int> 
#define mpr make_pair

typedef long long ll;

const int maxn = 2e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;

int n, m, k;

struct dsu
{
	int par[maxn];
	dsu() {memset(par, -1, sizeof par);}
	void reset() {fill(par, par+k+3, -1);}	
	
	int get_par(int v)
	{
		if(par[v] < 0) return v;
		return par[v] = get_par(par[v]);		
	}
	
	void add(int u, int v)
	{
		u = get_par(u);
		v = get_par(v);
		
		if(u == v) return;
		if(par[u] < par[v]) swap(u,v);
		par[v] += par[u];
		par[u] = v;
	}
	
	bool ask(int u, int v) {return (get_par(u) == get_par(v));}
} dsu;

vector<pii> T[maxn];
int par[maxn][20], dp[maxn], st[maxn], sz[maxn], comp[maxn], p[maxn], mark[maxn], h[maxn], sum[maxn], Root, siz, num;

void dfs(int v)
{
	dp[Root] += sum[v] * p[v];
	comp[v] = num; siz += p[v]; sz[num] += p[v];
	
	mark[v] = 1;
	st[v] = p[v];
	for(int i = 1; (1<<i) <= h[v]; i++)
		par[v][i] = par[par[v][i-1]][i-1];
	for(auto e : T[v])
	{
		int u = e.F, w = e.S;
		if(!mark[u])
		{
			h[u] = h[v] + 1;
			sum[u] = sum[v] + w;
			par[u][0] = v;
			dfs(u);
			st[v] += st[u];
		}
	}
}

void dfs_up(int v, int c)
{
	if(v != Root) dp[v] = dp[par[v][0]] + c * (siz - 2 * st[v]);
	for(auto e : T[v])
	{
		int u = e.F, w = e.S;
		if(u != par[v][0])
			dfs_up(u,w);
	}
}

int get_par(int v, int he)
{
	int i = 0;
	while(he)
	{
		if(he&1) v = par[v][i];
		he >>= 1;
		i++;
	}
	return v;
}

int lca(int u, int v)
{
	if(h[u] > h[v]) swap(u,v);
	v = get_par(v,h[v]-h[u]);
	if(u == v) return v;
	
	for(int i = 19; i >= 0; i--)
		if(par[v][i] != par[u][i])
		{
			v = par[v][i];
			u = par[u][i];
		}
	return par[v][0];
}

int dis(int u, int v)
{
	return sum[v] + sum[u] - 2 * sum[lca(u,v)];
}


vector<pair<int,pii>> Tree[22];
int pa[maxn], W[maxn], Sm[maxn], yal[maxn], stt[maxn];
void dfs_T(int v)
{
	yal[1] = 1;
	W[v] = inf;
	stt[v] = sz[v];
	for(auto e : Tree[v])
	{
		int u = e.F, v1 = e.S.F, u1 = e.S.S;
		if(u != pa[v])
		{
			pa[u] = v;
			dfs_T(u);
			stt[v] += stt[u];
		}
	}
}

ll ans = 0;
void reset() 
{
	ans = 0;
	dsu.reset(); 
	for(int i = 1; i <= k; i++) 
	{
		Tree[i].clear();
		W[i] = inf;
		pa[i] = 0;
		Sm[i] = 0;
		yal[i] = 0;
		stt[i] = 0;
	}
}

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	
	cin>> n >> m >> k;
	vector<pair<int,pii>> edge, Bedge; vector<pii> Redge;
	for(int i = 1, u, v, c; i <= m; i++)
	{
		cin>> u >> v >> c;
		edge.push_back({c,{u,v}});
	}		
	sort(edge.begin(), edge.end());
	
	for(int i = 1, u, v; i <= k; i++)
	{
		cin>> u >> v;
		Redge.push_back({u,v});
		dsu.add(u,v);
	}
	
	for(auto e : edge)	
	{
		int u = e.S.F, v = e.S.S, w = e.F;
		if(!dsu.ask(u,v)) 
		{
			T[u].push_back({v,w});
			T[v].push_back({u,w});
			dsu.add(u,v);
		}
		else Bedge.push_back(e);
	}
	for(int i = 1; i <= n; i++) cin>> p[i];	
	
		
	// comp[Root = 1] = 1
	for(int i = 1; i <= n; i++)
		if(!mark[i]) 
		{
			num++; siz = 0;
			Root = i;
			dfs(i);
			dfs_up(i,0);
		}
	
	ll last_ans = 0;
	for(int msk = 0; msk < (1<<k); msk++)
	{
		// in k ta dori nabashano ham bayad check koni
		
		reset();
		for(int i = 0; i < k; i++)
			if((1<<i) & msk)	
			{	
				int u = comp[Redge[i].F], v = comp[Redge[i].S];
				int u1 = Redge[i].F, v1 = Redge[i].S;
				dsu.add(u,v);
				Tree[u].push_back({v,{u1,v1}});
				Tree[v].push_back({u,{v1,u1}});
			}		
		
		for(auto e : Bedge)
		{
			int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
			int u1 = e.S.F, v1 = e.S.S;
			if(!dsu.ask(u,v)) 
			{
				dsu.add(u,v);
				Tree[u].push_back({v,{u1,v1}});
				Tree[v].push_back({u,{v1,u1}});
			}
		}
		
		dfs_T(1);
		
		for(auto e : Bedge)
		{	
			int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
			bool seen[k+2];
			memset(seen, 0, sizeof seen);
			while(u != 1)
			{	
				(seen[u] ^= 1);
				u = pa[u];
			}		
			while(v != 1)
			{
				(seen[v] ^= 1);
				v = pa[v];
			}	
			for(int i = 1; i <= k+1; i++)
				if(seen[i]) W[i] = min(W[i],w);			
			
			if(u == pa[v]) W[v] = 0;
			if(v == pa[u]) W[u] = 0;
		}	
		
		for(int i = 2; i <= k+1; i++) ans += stt[i] * W[i];
		last_ans = max(last_ans, ans);
	}
	
	cout<< last_ans;
}

Compilation message (stderr)

toll.cpp: In function 'void dfs_T(long long int)':
toll.cpp:124:16: warning: unused variable 'v1' [-Wunused-variable]
   int u = e.F, v1 = e.S.F, u1 = e.S.S;
                ^~
toll.cpp:124:28: warning: unused variable 'u1' [-Wunused-variable]
   int u = e.F, v1 = e.S.F, u1 = e.S.S;
                            ^~
toll.cpp: In function 'int main()':
toll.cpp:212:8: warning: unused variable 'w' [-Wunused-variable]
    int w = e.F, u = comp[e.S.F], v = comp[e.S.S];
        ^

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