oj.uz

Submission #129140

# Submission time Handle Problem Language Result Execution time Memory
129140 2019-07-11T18:02:22 Z TadijaSebez Toll (APIO13_toll) C++11
78 / 100
 2500 ms 8404 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],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];
	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;
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];
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 v:E[u]) if(v!=p)
	{
		DFS(v,u);
		sub[u]+=sub[v];
	}
}
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 AddEdge(int u, int v){ E[u].pb(v);E[v].pb(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++)
	{
		for(int i=1;i<=nsz;i++) T.p[i]=i,my[i]=0,E[i].clear();
		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];
			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

toll.cpp: In function 'int main()':
toll.cpp:69: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:70: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:72: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:73: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 6 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 6 ms 3452 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 6 ms 3452 KB Output is correct
5 Correct 9 ms 3576 KB Output is correct
6 Correct 9 ms 3576 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 6 ms 3452 KB Output is correct
5 Correct 9 ms 3576 KB Output is correct
6 Correct 9 ms 3576 KB Output is correct
7 Correct 312 ms 8404 KB Output is correct
8 Correct 296 ms 8360 KB Output is correct
9 Correct 293 ms 8312 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3576 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 6 ms 3452 KB Output is correct
5 Correct 9 ms 3576 KB Output is correct
6 Correct 9 ms 3576 KB Output is correct
7 Correct 312 ms 8404 KB Output is correct
8 Correct 296 ms 8360 KB Output is correct
9 Correct 293 ms 8312 KB Output is correct
10 Execution timed out 2545 ms 8360 KB Time limit exceeded
11 Halted 0 ms 0 KB -