oj.uz

Submission #129162

# Submission time Handle Problem Language Result Execution time Memory
129162 2019-07-11T18:29:52 Z TadijaSebez Toll (APIO13_toll) C++11
100 / 100
 2090 ms 15228 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3960 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3960 KB Output is correct
5 Correct 8 ms 4088 KB Output is correct
6 Correct 8 ms 4088 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3960 KB Output is correct
5 Correct 8 ms 4088 KB Output is correct
6 Correct 8 ms 4088 KB Output is correct
7 Correct 275 ms 8816 KB Output is correct
8 Correct 284 ms 8844 KB Output is correct
9 Correct 277 ms 8956 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 6 ms 3960 KB Output is correct
5 Correct 8 ms 4088 KB Output is correct
6 Correct 8 ms 4088 KB Output is correct
7 Correct 275 ms 8816 KB Output is correct
8 Correct 284 ms 8844 KB Output is correct
9 Correct 277 ms 8956 KB Output is correct
10 Correct 1702 ms 8844 KB Output is correct
11 Correct 2080 ms 15228 KB Output is correct
12 Correct 2090 ms 15208 KB Output is correct