oj.uz

답안 #129155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129155 2019-07-11T18:23:40 Z TadijaSebez 통행료 (APIO13_toll) C++11
78 / 100
 2500 ms 8568 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,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]),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<=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:53: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:54: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:56: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:57: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 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 3500 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 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 3500 KB Output is correct
5 Correct 8 ms 3576 KB Output is correct
6 Correct 8 ms 3732 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 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 3500 KB Output is correct
5 Correct 8 ms 3576 KB Output is correct
6 Correct 8 ms 3732 KB Output is correct
7 Correct 284 ms 8552 KB Output is correct
8 Correct 281 ms 8440 KB Output is correct
9 Correct 286 ms 8568 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 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 3500 KB Output is correct
5 Correct 8 ms 3576 KB Output is correct
6 Correct 8 ms 3732 KB Output is correct
7 Correct 284 ms 8552 KB Output is correct
8 Correct 281 ms 8440 KB Output is correct
9 Correct 286 ms 8568 KB Output is correct
10 Execution timed out 2540 ms 8540 KB Time limit exceeded
11 Halted 0 ms 0 KB -