Submission #129162

#	Time	Username	Problem	Language	Result	Execution time	Memory
129162		TadijaSebez	Toll (APIO13_toll)	C++11	100 / 100	2090 ms	15228 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int M=300050;
const int K=22;
struct DSU
{
	ll sz[N];
	int p[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=0;}
	DSU(){ init();}
	int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
	void Union(int x, int y)
	{
		x=Find(x);y=Find(y);
		sz[y]+=sz[x];
		p[x]=y;
	}
} DS1,DS2,DS3;
struct SimpleDSU
{
	int p[K*2];
	void init(){ for(int i=0;i<K*2;i++) p[i]=i;}
	SimpleDSU(){ init();}
	int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} T,F;
int a[M],b[M],c[M],id[M],x[K],y[K];
bool was[N];
int new_name[N];
ll sz[N],sub[K*2];
int dep[K*2],my[K*2],jmp[K*2];
int f[K*4],go[K*4],fir[K*2],tsz;
void DFS(int u, int p)
{
	sub[u]=sz[u];
	dep[u]=dep[p]+1;
	jmp[u]=p;
	for(int i=fir[u];i;i=go[i]) if(f[i]!=p)
	{
		DFS(f[i],u);
		sub[u]+=sub[f[i]];
	}
}
void Add(int u, int v){ f[++tsz]=v;go[tsz]=fir[u];fir[u]=tsz;}
void AddEdge(int u, int v){ Add(u,v);Add(v,u);}
int main()
{
	int n,m,k;
	scanf("%i %i %i",&n,&m,&k);
	for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),id[i]=i;
	sort(id+1,id+1+m,[&](int i, int j){ return c[i]<c[j];});
	for(int i=1;i<=k;i++)
	{
		scanf("%i %i",&x[i],&y[i]);
		DS3.Union(x[i],y[i]);
	}
	for(int i=1;i<=n;i++) scanf("%lld",&DS1.sz[i]);
	vector<int> es;
	for(int j=1;j<=m;j++)
	{
		int i=id[j];
		if(DS2.Find(a[i])!=DS2.Find(b[i]))
		{
			DS2.Union(a[i],b[i]);
			if(DS3.Find(a[i])!=DS3.Find(b[i]))
			{
				DS3.Union(a[i],b[i]);
				DS1.Union(a[i],b[i]);
			}
			else es.pb(i);
		}
	}
	int nsz=0;
	for(int i=1;i<=n;i++)
	{
		if(!was[DS1.Find(i)])
		{
			was[DS1.Find(i)]=1;
			new_name[DS1.Find(i)]=++nsz;
			sz[nsz]=DS1.sz[DS1.Find(i)];
		}
	}
	for(int i:es)
	{
		a[i]=new_name[DS1.Find(a[i])];
		b[i]=new_name[DS1.Find(b[i])];
	}
	for(int i=1;i<=k;i++)
	{
		x[i]=new_name[DS1.Find(x[i])];
		y[i]=new_name[DS1.Find(y[i])];
	}
	ll ans=0;
	for(int mask=1;mask<(1<<k);mask++)
	{
		for(int i=1;i<=tsz;i++) go[i]=0;
		tsz=0;
		for(int i=1;i<=nsz;i++) T.p[i]=i,F.p[i]=i,my[i]=fir[i]=0;
		bool ok=1;
		for(int i=1;i<=k;i++) if(mask>>(i-1)&1)
		{
			if(T.Find(x[i])!=T.Find(y[i]))
			{
				T.Union(x[i],y[i]);
				AddEdge(x[i],y[i]);
			}
			else{ ok=0;break;}
		}
		if(!ok) continue;
		vector<int> up;
		for(int i:es)
		{
			if(T.Find(a[i])!=T.Find(b[i]))
			{
				T.Union(a[i],b[i]);
				AddEdge(a[i],b[i]);
			}
			else up.pb(i);
		}
		DFS(1,0);
		for(int i:up)
		{
			int u=F.Find(a[i]),v=F.Find(b[i]);
			while(u!=v)
			{
				if(dep[u]>dep[v])
				{
					if(!my[u]) my[u]=i;
					F.Union(u,jmp[u]);
					u=F.Find(u);
				}
				else
				{
					if(!my[v]) my[v]=i;
					F.Union(v,jmp[v]);
					v=F.Find(v);
				}
			}
		}
		ll sum=0;
		for(int i=1;i<=k;i++) if(mask>>(i-1)&1)
		{
			int u=x[i];
			if(dep[u]<dep[y[i]]) u=y[i];
			sum+=(ll)c[my[u]]*sub[u];
		}
		ans=max(ans,sum);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:53:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i",&a[i],&b[i],&c[i]),id[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
toll.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:60:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld",&DS1.sz[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~

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