oj.uz

Submission #476986

# Submission time Handle Problem Language Result Execution time Memory
476986 2021-09-29T16:41:24 Z Jasiekstrz timeismoney (balkan11_timeismoney) C++17
50 / 100
 2000 ms 58444 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==p1 || p3==p2)
		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
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Execution timed out 2085 ms 58444 KB Time limit exceeded
5 Execution timed out 2080 ms 13048 KB Time limit exceeded
6 Execution timed out 2066 ms 12368 KB Time limit exceeded
7 Execution timed out 2059 ms 3372 KB Time limit exceeded
8 Execution timed out 2074 ms 1072 KB Time limit exceeded
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 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 4 ms 332 KB Output is correct
15 Correct 4 ms 328 KB Output is correct
16 Execution timed out 2063 ms 3284 KB Time limit exceeded
17 Execution timed out 2080 ms 1764 KB Time limit exceeded
18 Execution timed out 2085 ms 1604 KB Time limit exceeded
19 Execution timed out 2070 ms 952 KB Time limit exceeded
20 Execution timed out 2080 ms 860 KB Time limit exceeded