oj.uz

Submission #122444

# Submission time Handle Problem Language Result Execution time Memory
122444 2019-06-28T08:36:53 Z 임유진(#2991) Toll (APIO13_toll) C++14
34 / 100
 4 ms 404 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>

using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;

#define MAXN 35
#define MAXM 55
#define MAXK 15

const int INF=1e6+5;
int A[MAXM], B[MAXM], C[MAXM];
int p[MAXN];
int uni[MAXN];
vector<pii> e[MAXN];
int dp[MAXN], dep[MAXN];
pii par[MAXN];

bool cmp(int a, int b){
	return C[a]<C[b];
}

int guni(int x){
	if(x==uni[x]) return x;
	return uni[x]=guni(uni[x]);
}

void dfs(int x){
	//printf("dfs(%d), par[%d]=(%d, %d)\n", x, x, par[x].first, par[x].second);
	dp[x] = p[x];
	for(auto a : e[x]) if( dp[a.first] == 0){
		par[a.first]=make_pair(x, a.second);
		dep[a.first] = dep[x] + 1;
		dfs(a.first);
		dp[x] += dp[a.first];
	}
	//printf("dp[%d]=%d\n", x, dp[x]);
}

int main(){
	int N, M, K;
	int x[MAXK], y[MAXK];
	int es[MAXM];
	int v[MAXK];
	bitset<MAXN> chk;
	lint ans=0;

	scanf("%d%d%d", &N, &M, &K);
	for(int i=0; i<M; i++) scanf("%d%d%d", A+i, B+i, C+i);
	for(int i=0; i<K; i++) scanf("%d%d", x+i, y+i);
	for(int i=1; i<=N; i++) scanf("%d", p+i);

	for(int i=0; i<M; i++) es[i]=i;
	sort(es, es+M, cmp);

	for(int i=1; i<(1<<K); i++){
		bool ava=true;
		for(int j=1; j<=N; j++) {
			uni[j]=j;
			e[j].clear();
		}
		for(int j=0; j<K; j++) if((1<<j)&i) {
			if(guni(x[j])==guni(y[j])){
				ava=false;
				break;
			}
			uni[guni(x[j])] = guni(y[j]);
			e[x[j]].push_back( make_pair(y[j], j) );
			e[y[j]].push_back( make_pair(x[j], j) );
			v[j] = INF;
		}
		if(!ava) continue;
		//printf("i=%d\n", i);

		for(int j=0; j<M; j++) chk[j]=false;
		for(int j=0; j<M; j++) if(guni(A[es[j]]) != guni(B[es[j]])) {
			uni[guni(A[es[j]])] = guni(B[es[j]]);
			e[A[es[j]]].push_back(make_pair(B[es[j]], -1));
			e[B[es[j]]].push_back(make_pair(A[es[j]], -1));
			chk[j] = true;
		}
		for(int j=1; j<=N; j++) dp[j] = 0;
		dep[1] = 0;
		dfs(1);
		
		for(int j=0; j<M; j++) if(!chk[j]) {
			int r = A[es[j]], s = B[es[j]];
			//printf("r=%d, s=%d\n", r, s);
			while(dep[r] > dep[s]){
				if(par[r].second != -1) v[ par[r].second ] = min( v[ par[r].second ], C[es[j]] );
				r = par[r].first;
			}
			while(dep[s] > dep[r]){
				if( par[s].second != -1) v[ par[s].second ] = min( v[ par[s].second ], C[es[j]] );
				s = par[s].first;
			}
			while( r != s ) {
				if( par[s].second != -1) v[ par[s].second ] = min( v[ par[s].second ], C[es[j]] );
				s = par[s].first;
				if( par[r].second != -1) v[ par[r].second ] = min( v[ par[r].second ], C[es[j]] );
				r = par[r].first;
			}
		}

		//for(int j=0; j<K; j++) if((1<<j)&i) printf("v[%d]=%d\n", j, v[j]);

		lint sum = 0;
		for(int j=0; j<K; j++) if((1<<j) & i) sum += (lint)v[j] * min(dp[x[j]], dp[y[j]]);
		ans=max(ans, sum);
	}
	
	printf("%lld", 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("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:54:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<M; i++) scanf("%d%d%d", A+i, B+i, C+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:55:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<K; i++) scanf("%d%d", x+i, y+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:56:31: 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("%d", p+i);
                          ~~~~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Execution timed out 2 ms 404 KB Time limit exceeded (wall clock)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Execution timed out 2 ms 404 KB Time limit exceeded (wall clock)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Execution timed out 2 ms 404 KB Time limit exceeded (wall clock)
6 Halted 0 ms 0 KB -