oj.uz

답안 #483110

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483110 2021-10-27T17:22:28 Z Koosha_mv 시간이 돈 (balkan11_timeismoney) C++14
40 / 100
 1257 ms 372 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
#define int ll

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,N){
		f(j,0,N){
			v.clear();
			f(k,0,m){
				v.pb(mp((a[k]+i)*(b[k]+j),k));
			}
			find_mst();
		}
	}
}

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: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   41 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
timeismoney.cpp:41:2: note: in expansion of macro 'f'
   41 |  f(i,0,v.size()){
      |  ^
timeismoney.cpp: At global scope:
timeismoney.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:7:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   80 |  f(i,0,vans.size()){
      |    ~~~~~~~~~~~~~~~             
timeismoney.cpp:80:2: note: in expansion of macro 'f'
   80 |  f(i,0,vans.size()){
      |  ^

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1074 ms 332 KB Output is correct
2 Correct 78 ms 204 KB Output is correct
3 Correct 117 ms 300 KB Output is correct
4 Correct 324 ms 312 KB Output is correct
5 Incorrect 365 ms 204 KB Output isn't correct
6 Incorrect 97 ms 204 KB Output isn't correct
7 Incorrect 216 ms 204 KB Output isn't correct
8 Incorrect 317 ms 332 KB Output isn't correct
9 Correct 80 ms 204 KB Output is correct
10 Correct 192 ms 204 KB Output is correct
11 Correct 129 ms 300 KB Output is correct
12 Correct 402 ms 204 KB Output is correct
13 Incorrect 399 ms 204 KB Output isn't correct
14 Incorrect 81 ms 204 KB Output isn't correct
15 Incorrect 194 ms 304 KB Output isn't correct
16 Incorrect 85 ms 304 KB Output isn't correct
17 Incorrect 1257 ms 332 KB Output isn't correct
18 Incorrect 724 ms 324 KB Output isn't correct
19 Incorrect 410 ms 372 KB Output isn't correct
20 Incorrect 169 ms 320 KB Output isn't correct