Submission #352280

#	Time	Username	Problem	Language	Result	Execution time	Memory
352280		arnold518	Toll (APIO13_toll)	C++14	78 / 100	434 ms	163840 KiB

toll

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
const int MAXM = 3e5;
const int MAXK = 20;
 
int N, M, K;
 
struct Edge
{
	int u, v, w;
};
Edge E[MAXM+10];
pii A[MAXK+10];
ll B[MAXN+10];
 
struct UF
{
	int par[MAXN+10], sz[MAXN+10];
	void init()
	{
		memset(par, -1, (N+1)<<2);
		memset(sz, 0, (N+1)<<2);
	}
	inline int Find(int x)
	{
		if(-1==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(sz[x]>sz[y]) swap(x, y);
		if(sz[x]==sz[y]) sz[y]++;
		par[x]=y;
	}
}uf, uf2;
 
ll ans, val=0;
vector<pii> adj2[MAXN+10];
vector<int> adj[MAXN+10];
int root[MAXN+10];
 
ll sz[MAXN+10];
vector<int> ST;

int col[MAXN+10];
ll D[MAXN+10];
 
int par[30][MAXN+10], dep[MAXN+10], L[MAXN+10], cnt;
 
inline void dfs3(int now, int bef, int d)
{
	L[now]=++cnt;
	par[0][now]=bef;
	dep[now]=d;
	for(auto nxt : adj2[now])
	{
		if(nxt.first==bef) continue;
		dfs3(nxt.first, now, d+1);
	}
}
 
int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(register int i=20; i>=0; i--) if(dep[u]<=dep[par[i][v]]) v=par[i][v];
	if(u==v) return u;
	for(register int i=20; i>=0; i--) if(par[i][u]!=par[i][v]) u=par[i][u], v=par[i][v];
	return par[0][u];
}
 
int par2[MAXN+10];
int dep2[MAXN+10];
int Q[MAXN+10];
 
inline void dfs4(int now, int bef, int d)
{
	sz[now]=B[now];
	par2[now]=bef;
	dep2[now]=d;
	for(auto nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs4(nxt, now, d+1);
		sz[now]+=sz[nxt];
	}
}
 
int main()
{
	scanf("%d%d%d", &N, &M, &K);
	for(register int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
	for(register int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
	for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
 
	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
	{
		return p.w<q.w;
	});
 
	uf.init();
	vector<Edge> EE;
	for(register int i=1; i<=M; i++)
	{
		if(uf.Find(E[i].u)==uf.Find(E[i].v)) continue;
		uf.Union(E[i].u, E[i].v);
		EE.push_back(E[i]);
	}
	for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
	M=EE.size();
	EE.clear();
	assert(M==N-1);
 
	for(register int i=1; i<=M; i++)
	{
		adj2[E[i].u].push_back({E[i].v, E[i].w});
		adj2[E[i].v].push_back({E[i].u, E[i].w});
	}
 
	dfs3(1, 1, 1);
	for(register int i=1; i<=20; i++) for(register int j=1; j<=N; j++) par[i][j]=par[i-1][par[i-1][j]];
 
	vector<int> VV;
	VV.push_back(1);
	for(register int i=0; i<K; i++)
	{
		VV.push_back(A[i].first);
		VV.push_back(A[i].second);
	}
	sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
	{
		return L[p]<L[q];
	});
	VV.erase(unique(VV.begin(), VV.end()), VV.end());
 
	int t=VV.size();
	for(register int i=0; i+1<t; i++) VV.push_back(lca(VV[i], VV[i+1]));
 
	sort(VV.begin(), VV.end(), [&](const int &p, const int &q)
	{
		return L[p]<L[q];
	});
	VV.erase(unique(VV.begin(), VV.end()), VV.end());
	sort(VV.begin(), VV.end());
 
	uf.init();
	for(auto it : VV) col[it]=it;
 
	for(register int i=1; i<=N; i++) D[i]=B[i];
	for(register int i=1; i<=M; i++)
	{
		if(col[uf.Find(E[i].u)] && col[uf.Find(E[i].v)])
		{
			EE.push_back(E[i]);
		}
		else
		{
			int p=uf.Find(E[i].u), q=uf.Find(E[i].v);
			D[p]+=D[q];
			uf.par[q]=p;
			col[p]|=col[q];
		}
	}
 
	for(auto &it : EE)
	{
		it.u=lower_bound(VV.begin(), VV.end(), col[uf.Find(it.u)])-VV.begin()+1;
		it.v=lower_bound(VV.begin(), VV.end(), col[uf.Find(it.v)])-VV.begin()+1;
	}
	for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
	M=EE.size();
 
	for(register int i=0; i<K; i++)
	{
		A[i].first=lower_bound(VV.begin(), VV.end(), A[i].first)-VV.begin()+1;
		A[i].second=lower_bound(VV.begin(), VV.end(), A[i].second)-VV.begin()+1;
	}
 
	for(register int i=0; i<VV.size(); i++)
	{
		B[i+1]=D[uf.Find(VV[i])];
	}
	N=VV.size();
/*
	printf("VV\n");
	for(auto it : VV) printf("%d ", it); printf("\n");
	printf("E\n");
	for(register int i=1; i<=M; i++) printf("%d %d %d\n", E[i].u, E[i].v, E[i].w);
	printf("B\n");
	for(register int i=1; i<=N; i++) printf("%lld ", B[i]); printf("\n");
	printf("A\n");
	for(register int i=0; i<K; i++) printf("%d %d\n", A[i].first, A[i].second);
*/
 
	assert(N<=100);
	for(register int i=1; i<(1<<K); i++)
	{
		uf.init();
		bool flag=true;
		for(register int it=0; it<K; it++)
		{
			if(!(i&(1<<it))) continue;
			if(uf.Find(A[it].first)==uf.Find(A[it].second))
			{
				flag=false;
				break;
			}
			uf.Union(A[it].first, A[it].second);
			adj[A[it].first].push_back(A[it].second);
			adj[A[it].second].push_back(A[it].first);
		}
 
		if(!flag)
		{
			for(register int j=1; j<=N; j++) adj[j].clear();
			continue;
		}
 
		uf2.init();
		for(register int j=1; j<=N; j++) root[j]=j;

		for(register int j=1; j<=M; j++)
		{
			if(uf.Find(E[j].u)==uf.Find(E[j].v))
			{
				Q[j]=1;
			}
			else
			{
				Q[j]=0;
				uf.Union(E[j].u, E[j].v);
				adj[E[j].u].push_back(E[j].v);
				adj[E[j].v].push_back(E[j].u);
				//printf("!%d %d %d\n", E[j].u, E[j].v, 0);
			}
		}
 
		if(K<=15) dfs4(1, 1, 1);

		val=0;
		for(register int j=1; j<=M; j++)
		{
			if(Q[j])
			{
				int u=E[j].u, v=E[j].v;
				u=root[uf2.Find(u)]; v=root[uf2.Find(v)];
				while(u!=v)
				{
					if(dep2[u]>dep2[v]) swap(u, v);
					val+=sz[v]*E[j].w;
					int t2=root[uf2.Find(par2[v])];
					uf2.Union(v, par2[v]);
					root[uf2.Find(v)]=t2;
					v=t2;
				}
			}
			else
			{
				int uu=root[uf2.Find(E[j].u)], vv=root[uf2.Find(E[j].v)];
				if(dep2[uu]>dep2[vv]) swap(uu, vv);
				uf2.Union(vv, uu);
				root[uf2.Find(vv)]=uu;
			}
		}

		ans=max(ans, val);

		for(register int j=1; j<=N; j++) vector<int>().swap(adj[j]);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:104:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  104 |  for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
      |                                          ~^   ~~~~~
      |                                           |   |
      |                                           |   ll* {aka long long int*}
      |                                           int*
      |                                          %lld
toll.cpp:119:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
      |                        ~^~~~~~~~~~
toll.cpp:180:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |  for(register int i=0; i<EE.size(); i++) E[i+1]=EE[i];
      |                        ~^~~~~~~~~~
toll.cpp:189:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |  for(register int i=0; i<VV.size(); i++)
      |                        ~^~~~~~~~~~
toll.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  scanf("%d%d%d", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:102:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  for(register int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:103:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  for(register int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:104:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |  for(register int i=1; i<=N; i++) scanf("%d", &B[i]);
      |                                   ~~~~~^~~~~~~~~~~~~

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