oj.uz

Submission #476987

# Submission time Handle Problem Language Result Execution time Memory
476987 2021-09-29T16:46:50 Z Jasiekstrz timeismoney (balkan11_timeismoney) C++17
100 / 100
 489 ms 580 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=200;
const int C=255;
const int M=1e4;
struct Edge
{
	int a,b;
	long long c1,c2;
};
Edge edg[M+10];
int fau[N+10];
long long ans1=N*C+7,ans2=N*C+7;
vector<pair<int,int>> ans;
void clr_fau(int n)
{
	for(int i=0;i<=n;i++)
		fau[i]=i;
	return;
}
int f(int x)
{
	return (fau[x]==x ? x:fau[x]=f(fau[x]));
}
void u(int x,int y)
{
	fau[f(x)]=f(y);
	return;
}
pair<long long,long long> mst(int n,int m,long long k1,long long k2)
{
	long long w1=0,w2=0;
	vector<pair<int,int>> in_mst;
	clr_fau(n);
	sort(edg+1,edg+m+1,[k1,k2](Edge e1,Edge e2){ return e1.c1*k1+e1.c2*k2<e2.c1*k1+e2.c2*k2; });
	for(int ei=1;ei<=m;ei++)
	{
		auto e=edg[ei];
		if(f(e.a)!=f(e.b))
		{
			u(e.a,e.b);
			w1+=e.c1;
			w2+=e.c2;
			in_mst.emplace_back(e.a,e.b);
		}
	}
	if(w1*w2<ans1*ans2)
	{
		ans1=w1;
		ans2=w2;
		ans=in_mst;
	}
	//cerr<<k1<<" "<<k2<<" -> "<<w1<<" "<<w2<<"\n";
	return {w1,w2};
}
void solve(int n,int m,pair<long long,long long> p1,pair<long long,long long> p2)
{
	auto p3=mst(n,m,p2.se-p1.se,p1.fi-p2.fi);
	if((p3.fi-p1.fi)*(p2.se-p1.se)-(p2.fi-p1.fi)*(p3.se-p1.se)==0)
		return;
	solve(n,m,p1,p3);
	solve(n,m,p3,p2);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>edg[i].a>>edg[i].b>>edg[i].c1>>edg[i].c2;
	solve(n,m,mst(n,m,0,1),mst(n,m,1,0));
	cout<<ans1<<" "<<ans2<<"\n";
	for(auto [a,b]:ans)
		cout<<a<<" "<<b<<"\n";
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 5 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 57 ms 356 KB Output is correct
17 Correct 60 ms 352 KB Output is correct
18 Correct 57 ms 332 KB Output is correct
19 Correct 467 ms 536 KB Output is correct
20 Correct 489 ms 580 KB Output is correct