oj.uz

답안 #483106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483106 2021-10-27T17:14:24 Z Koosha_mv 시간이 돈 (balkan11_timeismoney) C++14
40 / 100
 887 ms 328 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,Mx=55000;

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,Mx){
		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()){
      |  ^

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 887 ms 304 KB Output is correct
2 Correct 58 ms 204 KB Output is correct
3 Correct 102 ms 204 KB Output is correct
4 Correct 248 ms 312 KB Output is correct
5 Incorrect 302 ms 312 KB Output isn't correct
6 Incorrect 73 ms 204 KB Output isn't correct
7 Incorrect 164 ms 204 KB Output isn't correct
8 Incorrect 248 ms 304 KB Output isn't correct
9 Correct 59 ms 204 KB Output is correct
10 Correct 125 ms 204 KB Output is correct
11 Correct 101 ms 204 KB Output is correct
12 Correct 266 ms 328 KB Output is correct
13 Incorrect 246 ms 300 KB Output isn't correct
14 Incorrect 73 ms 204 KB Output isn't correct
15 Incorrect 135 ms 324 KB Output isn't correct
16 Incorrect 59 ms 312 KB Output isn't correct
17 Incorrect 734 ms 304 KB Output isn't correct
18 Incorrect 423 ms 300 KB Output isn't correct
19 Incorrect 264 ms 204 KB Output isn't correct
20 Incorrect 129 ms 204 KB Output isn't correct