oj.uz

Submission #96247

# Submission time Handle Problem Language Result Execution time Memory
96247 2019-02-07T12:52:18 Z Retro3014 Toll (APIO13_toll) C++17
16 / 100
 7 ms 2680 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define MAX_N 100000
#define MAX_M 300000
#define MAX_K 20
typedef long long ll;

int N, M, K;
struct EDGE{
	EDGE (int x, int y, int z) : x(x), y(y), z(z) {}
	int x, y, z;
	bool operator <(const EDGE &a)const{
		return z<a.z;
	}
};
vector<EDGE> edge, edge2;
/*struct EDGE2{
	EDGE2 (int x, int y) : x(x), y(y) {}
	int x, y;
};
vector<EDGE2> edge2;*/
vector<int> P;
vector<int> gp[MAX_N+1];
int g[MAX_N+1];

void init(){
	for(int i=1; i<=N; i++)	g[i] = i;
}

int find_g(int x){
	if(x==g[x])	return x;
	return g[x] = find_g(g[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	g[x] = y;
}

bool use[MAX_M+1];

void solve1(){
	int idx = -1;
	init();
	for(int i=0; i<edge.size(); i++){
		if(find_g(edge[i].x)==find_g(edge[i].y))	continue;
		union_g(edge[i].x, edge[i].y);
		use[i] = true;
		if(idx==-1 && find_g(edge2[0].x)==find_g(edge2[0].y)){
			idx = i;
			use[i] = false;
		}
	}
	//cout<<idx<<endl;
	init();
	for(int i=0; i<edge.size(); i++){
		if(!use[i])	continue;
		union_g(edge[i].x, edge[i].y);
	}
	ll ans=0;
	for(int i=1; i<=N; i++){
		if(find_g(i)==find_g(1))	continue;
		ans += (ll)P[i];
	}
	ans *= (ll)edge[idx].z;
	printf("%lld", ans);}

bool chk[MAX_K+1];
int p[MAX_N+1];

void dfs(int x){
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i]==p[x])	continue;
		p[gp[x][i]] = x;
		dfs(gp[x][i]);
	}
}
vector<int> idx;
ll answer;
int T;
ll dfs2(int x){
	ll sum = P[x];
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i]==p[x])	continue;
		sum+=dfs2(gp[x][i]);
	}
	for(int i=0; i<K; i++){
		if(((1<<i)&T)==0)	continue;
		if(edge2[i].y==x){
			answer += (ll)edge2[i].z * sum;
		}
	}
	return sum;
}

void solve2(){
	ll ans = 0;
	init();
	T = (1<<K);
	bool tf = false;
	while(T--){
		init();
		answer = 0;
		tf = false;
		for(int i=0; i<K; i++)	chk[i] = false;
		for(int i=0; i<M; i++)	use[i] = false;
		for(int i=0; i<edge.size(); i++){
			if(find_g(edge[i].x)==find_g(edge[i].y))	continue;
			union_g(edge[i].x, edge[i].y);
			use[i] = true;
			for(int j=0; j<K; j++){
				if((((1<<j)&T)!=0) && !chk[j] && find_g(edge2[j].x)==find_g(edge2[j].y)){
					edge2[j].z = edge[i].z;
					chk[j] = true;
					use[i] = false;
					break;
				}
			}
			for(int j=0; j<K; j++){
				if((((1<<j)&T)!=0) && !chk[j] && find_g(edge2[j].x)==find_g(edge2[j].y)){
					tf = true;
					break;
				}
			}
			if(tf)	break;
		}
		for(int i=0; i<K; i++){
			if((((1<<i)&T)!=0) && !chk[i]){
				tf = true;
				break;
			}
		}
		if(tf)	continue;
		for(int i=1; i<=N; i++){
			gp[i].clear();
		}
		for(int i=0; i<edge.size(); i++){
			if(!use[i])	continue;
			gp[edge[i].x].push_back(edge[i].y); gp[edge[i].y].push_back(edge[i].x);
		}
		for(int i=0; i<K; i++){
			if(((1<<i)&T)==0)	continue;
			gp[edge2[i].x].push_back(edge2[i].y); gp[edge2[i].y].push_back(edge2[i].x);
		}
		//cout<<N<<' '<<M<<' '<<K<<endl;
		/*for(int i=1; i<=N; i++){
			for(int j=0; j<gp[i].size(); j++){
				printf("%d ", gp[i][j]);
			}
			printf("\n");
		}*/
		//for(int i=1; i<=N; i++)	p[i] = 0;
		dfs(1);
		for(int i=0; i<K; i++){
			if(((1<<i)&T)==0)	continue;
			if(edge2[i].y==p[edge2[i].x]){
				int tmp = edge2[i].y; edge2[i].y = edge2[i].x; edge2[i].x = tmp;
			}
		}
		dfs2(1);
		ans = max(ans, answer);
	}
	printf("%lld", ans);
}

int main(){
	scanf("%d%d%d", &N, &M, &K);
	for(int i=0; i<M; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		edge.push_back({a, b, c});
	}sort(edge.begin(), edge.end());
	for(int i=0; i<K; i++){
		int a, b;
		scanf("%d%d", &a, &b); edge2.push_back({a, b, 0});
	}P.push_back(0);
	for(int i=1; i<=N; i++){
		int a; scanf("%d", &a); P.push_back(a);
	}
	//if(N<=10 && M<=20 && K==1)	solve1();
	solve2();

	return 0;
}

Compilation message

toll.cpp: In function 'void solve1()':
toll.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
toll.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
toll.cpp: In function 'void dfs(int)':
toll.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
toll.cpp: In function 'll dfs2(int)':
toll.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
toll.cpp: In function 'void solve2()':
toll.cpp:111:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<edge.size(); i++){
                ~^~~~~~~~~~~~
toll.cpp:141:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<edge.size(); i++){
                ~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:171: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:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b); edge2.push_back({a, b, 0});
   ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:182:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a); P.push_back(a);
          ~~~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 7 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 7 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 7 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Incorrect 7 ms 2680 KB Output isn't correct
4 Halted 0 ms 0 KB -