Submission #129147

#	Time	Username	Problem	Language	Result	Execution time	Memory
129147		TadijaSebez	Toll (APIO13_toll)	C++11	16 / 100	2528 ms	3448 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],mark[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=mark[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;
		mark[y]|=mark[x];
	}
} DS1,DS2;
struct SimpleDSU
{
	int p[K*2],sz[K*2];
	void init(){ for(int i=0;i<K*2;i++) p[i]=i,sz[i]=1;}
	SimpleDSU(){ init();}
	int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
	void Union(int x, int y)
	{
		if(sz[x]>sz[y]) swap(x,y);
		p[x=Find(x)]=y=Find(y);
		sz[y]+=sz[x];
	}
} T;
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];
vector<int> E[K*2];
const int L=5;
int dep[K*2],par[K*2][L],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;
	//par[u][0]=p;
	jmp[u]=p;
	//for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(int i=fir[u];i;i=go[i]) if(f[i]!=p)
	{
		DFS(f[i],u);
		sub[u]+=sub[f[i]];
	}
}
/*int LCA(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}*/
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 Work(int u, int lca, int i)
{
	if(dep[u]<=dep[lca]) return u;
	if(!my[u]) my[u]=i;
	jmp[u]=Work(jmp[u],lca,i);
	return jmp[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]),DS1.mark[x[i]]=DS1.mark[y[i]]=1;
	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]))
		{
			if(DS1.mark[DS1.Find(a[i])]+DS1.mark[DS1.Find(b[i])]<2) DS1.Union(a[i],b[i]);
			else es.pb(i);
			DS2.Union(a[i],b[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=1;i<=m;i++)
	{
		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++)
	{
		tsz=0;
		for(int i=1;i<=nsz;i++) T.p[i]=i,my[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=a[i],v=b[i];
			vector<int> upd;
			while(1)
			{
				if(u==v) break;
				if(dep[u]>dep[v])
				{
					if(!my[u]) my[u]=i;
					upd.pb(u);
					u=jmp[u];
				}
				else
				{
					if(!my[v]) my[v]=i;
					upd.pb(v);
					v=jmp[v];
				}
			}
			for(int z:upd) jmp[z]=u;
			/*int lca=LCA(u,v);
			Work(u,lca,i);
			Work(v,lca,i);*/
			/*if(dep[u]<dep[v]) swap(u,v);
			for(;dep[u]>dep[v];u=par[u]) if(!my[u]) my[u]=i;
			for(;u!=v;u=par[u],v=par[v])
			{
				if(!my[u]) my[u]=i;
				if(!my[v]) my[v]=i;
			}*/
		}
		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:76: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:77: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:79:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=k;i++) scanf("%i %i",&x[i],&y[i]),DS1.mark[x[i]]=DS1.mark[y[i]]=1;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:80: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: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22