oj.uz

답안 #351645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351645 2021-01-20T06:08:56 Z arnold518 통행료 (APIO13_toll) C++14
16 / 100
 6 ms 4972 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 3e5;
const int MAXK = 20;

int N, M, K;

struct Edge
{
	int u, v, w;
};
Edge E[MAXM+10];
pii A[MAXK+10];
int B[MAXN+10];

struct UF
{
	int par[MAXN+10];
	vector<int> V[MAXN+10];
	void init()
	{
		for(int i=1; i<=N; i++)
		{
			par[i]=i;
			V[i].clear();
		}
	}
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(V[x].size()>V[y].size()) swap(x, y);
		for(auto it : V[x]) V[y].push_back(it);
		par[x]=y; V[x].clear();
	}
}uf;

ll ans, val=0;
vector<pii> adj[MAXN+10];

int sz[MAXN+10];
void dfs(int now, int bef, int k)
{
	sz[now]=B[now];
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, nxt.second);
		sz[now]+=sz[nxt.first];
	}
	//printf("?%d : %d\n", now, sz[now]);
	val+=(ll)sz[now]*k;
}

int main()
{
	scanf("%d%d%d", &N, &M, &K);
	for(int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
	for(int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
	for(int i=1; i<=N; i++) scanf("%d", &B[i]);

	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
	{
		return p.w<q.w;
	});
	
	uf.init();
	vector<Edge> EE;
	for(int i=1; i<=M; i++)
	{
		if(uf.Find(E[i].u)==uf.Find(E[i].v)) continue;
		uf.Union(E[i].u, E[i].v);
		EE.push_back(E[i]);
	}
	for(int i=0; i<EE.size(); i++) E[i+1]=EE[i];
	M=EE.size();
	assert(M==N-1);

	for(int i=0; i<(1<<K); i++)
	{
		vector<int> V;
		for(int j=0; j<K; j++)
		{
			if(i&(1<<j))
			{
				V.push_back(j);
			}
		}

		uf.init();
		bool flag=true;
		for(auto it : V)
		{
			if(uf.Find(A[it].first)==uf.Find(A[it].second))
			{
				flag=false;
				break;
			}
			uf.Union(A[it].first, A[it].second);
			uf.V[uf.Find(A[it].first)].push_back(it);
		}

		if(!flag) continue;

		int cnt=0;
		for(int j=1; j<=M; j++)
		{
			if(uf.Find(E[j].u)==uf.Find(E[j].v))
			{
				for(auto it : uf.V[uf.Find(E[j].u)])
				{
					cnt++;
					adj[A[it].first].push_back({A[it].second, E[j].w});
					adj[A[it].second].push_back({A[it].first, E[j].w});
					//printf("!!%d %d %d\n", A[it].first, A[it].second, E[j].w);
				}
				uf.V[uf.Find(E[j].u)].clear();
			}
			else
			{
				cnt++;
				uf.Union(E[j].u, E[j].v);
				adj[E[j].u].push_back({E[j].v, 0});
				adj[E[j].v].push_back({E[j].u, 0});
				//printf("!%d %d %d\n", E[j].u, E[j].v, 0);
			}
		}
		assert(cnt==N-1);

		val=0;
		dfs(1, 1, 0);
		//printf("%d : %lld\n", i, val);
		ans=max(ans, val);

		for(int i=1; i<=N; i++) adj[i].clear();
	}
	printf("%lld\n", ans);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=0; i<EE.size(); i++) E[i+1]=EE[i];
      |               ~^~~~~~~~~~
toll.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d%d%d", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:68:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  for(int i=1; i<=M; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:69:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  for(int i=0; i<K; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  for(int i=1; i<=N; i++) scanf("%d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 6 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 6 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 6 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 6 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -