oj.uz

Submission #36106

# Submission time Handle Problem Language Result Execution time Memory
36106 2017-12-05T17:26:06 Z mohammad_kilani Toll (APIO13_toll) C++14
56 / 100
 756 ms 2376 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 2000000000
const int N = 1010;
int n , m , k , prnt[N] , cur[N];
long long  current = 0 , comp[N];
vector< pair< pair<int,int> , pair<int,int> > > v;
vector< vector< pair<int, pair<int,int> > > > g;
pair<int,int> ed[30];

int Find(int u){
	if(u == prnt[u]) return u;
	return prnt[u] = Find(prnt[u]);
}

void min_tree(vector< pair< pair<int,int> ,pair<int,int> > > v, vector < vector< pair<int, pair<int,int> > > > &g){
	g.clear();
	g.resize(n+1);
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++) prnt[i] = i;
	for(int i=0;i<v.size();i++){
		int a = Find(prnt[v[i].second.first]);
		int b = Find(prnt[v[i].second.second]);
		if(a == b) continue;
		prnt[a] = b;
		g[v[i].second.first].push_back(make_pair(v[i].second.second,v[i].first));
		g[v[i].second.second].push_back(make_pair(v[i].second.first,v[i].first));
	}
}

void DFS2(int node,int prnt,int num){
	comp[node] = num;
	for(int i=0;i<g[node].size();i++){
		if(g[node][i].first != prnt) DFS2(g[node][i].first,node,num);
	}
}

long long get(int node,int node2){
	DFS2(node2,node,1);
	long long mn = oo;
	for(int i=0;i<v.size();i++){
		if(v[i].first.first == 0) continue;
		if(comp[v[i].second.first] == comp[v[i].second.second]) continue;
		mn = min(mn,(long long)v[i].first.first);
	}
	DFS2(node2,node,0);
	return mn;
}

long long DFS(int node,int prnt){
	long long all = 0 ;
	for(int i=0;i<g[node].size();i++){
		if(g[node][i].first == prnt) continue;
		long long res = DFS(g[node][i].first,node);
		if(g[node][i].second.second){
			current += res * get(node,g[node][i].first);
		}
		all += res;
	}
	return all + cur[node];
}

int main() {
	//freopen("in.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) prnt[i] = i ;
	for(int i=0;i<m;i++){
		int u ,V , c;
		scanf("%d%d%d",&u,&V,&c);
		v.push_back(make_pair(make_pair(c,0),make_pair(u,V)));
	}
	min_tree(v,g);
	for(int i=0;i<k;i++){
		scanf("%d%d",&ed[i].first,&ed[i].second);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&cur[i]);
	long long ans = 0 ;
	for(int i=0;i<(1 << k);i++){
		for(int j=0;j<k;j++){
			if((i >> j & 1) == 1) v.push_back(make_pair(make_pair(0,1),ed[j]));
		}
		min_tree(v,g);
		current = 0 ;
		DFS(1,-1);
		ans = max(ans,current);
		for(int j=0;j<k;j++){
			if((i >> j & 1) == 1) v.pop_back();
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message

toll.cpp: In function 'void min_tree(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >, std::vector<std::vector<std::pair<int, std::pair<int, int> > > >&)':
toll.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
               ^
toll.cpp: In function 'void DFS2(int, int, int)':
toll.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'long long int get(int, int)':
toll.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
               ^
toll.cpp: In function 'long long int DFS(int, int)':
toll.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'int main()':
toll.cpp:66:26: 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:70:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&u,&V,&c);
                           ^
toll.cpp:75:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&ed[i].first,&ed[i].second);
                                           ^
toll.cpp:78:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&cur[i]);
                      ^

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Correct 6 ms 2036 KB Output is correct
4 Correct 6 ms 2036 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Correct 6 ms 2036 KB Output is correct
4 Correct 6 ms 2036 KB Output is correct
5 Correct 756 ms 2376 KB Output is correct
6 Correct 446 ms 2376 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Correct 6 ms 2036 KB Output is correct
4 Correct 6 ms 2036 KB Output is correct
5 Correct 756 ms 2376 KB Output is correct
6 Correct 446 ms 2376 KB Output is correct
7 Runtime error 0 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Correct 6 ms 2036 KB Output is correct
4 Correct 6 ms 2036 KB Output is correct
5 Correct 756 ms 2376 KB Output is correct
6 Correct 446 ms 2376 KB Output is correct
7 Runtime error 0 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -