oj.uz

답안 #483105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483105 2021-10-27T17:12:05 Z Koosha_mv 시간이 돈 (balkan11_timeismoney) C++14
40 / 100
 315 ms 324 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,20000){
		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 315 ms 308 KB Output is correct
2 Correct 21 ms 316 KB Output is correct
3 Correct 35 ms 296 KB Output is correct
4 Correct 105 ms 204 KB Output is correct
5 Incorrect 102 ms 204 KB Output isn't correct
6 Incorrect 29 ms 204 KB Output isn't correct
7 Incorrect 60 ms 312 KB Output isn't correct
8 Incorrect 92 ms 324 KB Output isn't correct
9 Correct 28 ms 204 KB Output is correct
10 Correct 46 ms 204 KB Output is correct
11 Correct 34 ms 204 KB Output is correct
12 Correct 92 ms 304 KB Output is correct
13 Incorrect 90 ms 204 KB Output isn't correct
14 Incorrect 24 ms 204 KB Output isn't correct
15 Incorrect 49 ms 300 KB Output isn't correct
16 Incorrect 22 ms 320 KB Output isn't correct
17 Incorrect 266 ms 316 KB Output isn't correct
18 Incorrect 158 ms 300 KB Output isn't correct
19 Incorrect 101 ms 204 KB Output isn't correct
20 Incorrect 45 ms 204 KB Output isn't correct