oj.uz

Submission #1010757

# Submission time Handle Problem Language Result Execution time Memory
1010757 2024-06-29T10:35:40 Z vjudge1 timeismoney (balkan11_timeismoney) C++11
40 / 100
 4 ms 988 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,m,ai,bi,ti,ci,sum;
int par[201],rnk[201];
vector<pair<int,int> >v[201];
vector<pair<long long,pair<int,int> > >edging;
vector<pair<int,int> >answer;
int get(int x){
	if(par[x]==x)return x;
	return par[x]=get(par[x]);
}
void combine(int x,int y){
	x=get(x);
	y=get(y);
	if(x!=y){
		if(rnk[x]<rnk[y])swap(x,y);
		par[x]=y;
		if(rnk[x]==rnk[y])rnk[x]++;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)par[i]=i;
	for(int i=0;i<m;i++){
		cin>>ai>>bi>>ti>>ci;
		v[ai].push_back({bi,ci});
		v[bi].push_back({ai,ci});
		edging.push_back({ci,{ai,bi}});
	}
	sort(edging.begin(),edging.end());
	for(int i=0;i<m;i++){
		long long ci=edging[i].first;
		int ai=edging[i].second.first;
		int bi=edging[i].second.second;
		if(get(ai)!=get(bi)){
			answer.push_back({edging[i].second.first,edging[i].second.second});
			sum+=ci;
			combine(ai,bi);
		}
	}
	cout<<sum<<' '<<sum<<'\n';
	for(int i=0;i<answer.size();i++)cout<<answer[i].first<<' '<<answer[i].second<<'\n';
	return 0;
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<answer.size();i++)cout<<answer[i].first<<' '<<answer[i].second<<'\n';
      |              ~^~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 988 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 344 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 0 ms 344 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Incorrect 2 ms 348 KB Output isn't correct
19 Incorrect 4 ms 860 KB Output isn't correct
20 Incorrect 4 ms 860 KB Output isn't correct