답안 #483104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483104 2021-10-27T17:09:23 Z Koosha_mv 시간이 돈 (balkan11_timeismoney) C++14
40 / 100
79 ms 332 KB
#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=270,M=10101;

int n,m,ans1=1e9,ans2=1e9,s[N],t[N],a[N],b[N],par[N];
vector<pair<int,int> > v,mv,vans;

int Get_par(int u){
	if(par[u]<0) return u;
	return par[u]=Get_par(par[u]);
}
void merge(int u,int v){
	u=Get_par(u),v=Get_par(v);
	if(par[u]>par[v]) swap(u,v);
	par[u]+=par[v];
	par[v]=u;
}
void find_mst(){
	fill(par,par+N,-1);
	sort(v.begin(),v.end());
	mv.clear();
	int sum1=0,sum2=0;
	f(i,0,v.size()){
		int x=s[v[i].S],y=t[v[i].S];
		//cout<<x<<" "<<y<<endl;
		if(Get_par(x)!=Get_par(y)){
		//	eror(x);
			sum1+=a[v[i].S],sum2+=b[v[i].S];
			merge(x,y);
			mv.pb(mp(x,y));
		}
	}
	if(1ll*sum1*sum2<1ll*ans1*ans2){
		ans1=sum1,ans2=sum2;
		vans=mv;
	}
}
void solve(){
	f(i,0,5000){
		v.clear();
		f(j,0,m){
			v.pb(mp(a[j]+i*b[j],j));
		}
		find_mst();
	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	f(i,0,m){
		cin>>s[i]>>t[i]>>a[i]>>b[i];
	}
	solve();
	f(i,0,m){
		swap(a[i],b[i]);
	}
	solve();
	cout<<ans1<<" "<<ans2<<endl;
	f(i,0,vans.size()){
		cout<<vans[i].F<<" "<<vans[i].S<<endl;
	}
}
/*
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
*/

Compilation message

timeismoney.cpp: In function 'void find_mst()':
timeismoney.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   40 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
timeismoney.cpp:40:2: note: in expansion of macro 'f'
   40 |  f(i,0,v.size()){
      |  ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   77 |  f(i,0,vans.size()){
      |    ~~~~~~~~~~~~~~~             
timeismoney.cpp:77:2: note: in expansion of macro 'f'
   77 |  f(i,0,vans.size()){
      |  ^
# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 204 KB Output is correct
2 Correct 6 ms 312 KB Output is correct
3 Correct 8 ms 316 KB Output is correct
4 Correct 23 ms 320 KB Output is correct
5 Incorrect 26 ms 204 KB Output isn't correct
6 Incorrect 7 ms 204 KB Output isn't correct
7 Incorrect 17 ms 332 KB Output isn't correct
8 Incorrect 24 ms 332 KB Output isn't correct
9 Correct 6 ms 204 KB Output is correct
10 Correct 13 ms 204 KB Output is correct
11 Correct 9 ms 204 KB Output is correct
12 Incorrect 23 ms 320 KB Output isn't correct
13 Correct 23 ms 320 KB Output is correct
14 Incorrect 6 ms 204 KB Output isn't correct
15 Incorrect 12 ms 316 KB Output isn't correct
16 Incorrect 6 ms 204 KB Output isn't correct
17 Incorrect 66 ms 204 KB Output isn't correct
18 Incorrect 40 ms 204 KB Output isn't correct
19 Incorrect 24 ms 324 KB Output isn't correct
20 Incorrect 12 ms 316 KB Output isn't correct