oj.uz

Submission #956210

# Submission time Handle Problem Language Result Execution time Memory
956210 2024-04-01T10:15:16 Z Trisanu_Das Toll (APIO13_toll) C++17
56 / 100
 460 ms 824 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 of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
toll.cpp: In function 'void DFS2(int, int, int)':
toll.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  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 of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
toll.cpp: In function 'long long int DFS(int, int)':
toll.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i=0;i<g[node].size();i++){
      |              ~^~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d%d",&u,&V,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d",&ed[i].first,&ed[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d",&cur[i]);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 5 ms 348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 460 ms 824 KB Output is correct
6 Correct 291 ms 604 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 460 ms 824 KB Output is correct
6 Correct 291 ms 604 KB Output is correct
7 Runtime error 1 ms 344 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 460 ms 824 KB Output is correct
6 Correct 291 ms 604 KB Output is correct
7 Runtime error 1 ms 344 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -