oj.uz

Submission #476985

# Submission time Handle Problem Language Result Execution time Memory
476985 2021-09-29T16:38:05 Z Jasiekstrz timeismoney (balkan11_timeismoney) C++17
50 / 100
 2000 ms 62916 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;
	int c1,c2;
};
Edge edg[M+10];
int fau[N+10];
int 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<int,int> mst(int n,int m,int k1,int k2)
{
	int 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((long long)w1*w2<(long long)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<int,int> p1,pair<int,int> 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 332 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 2091 ms 62916 KB Time limit exceeded
5 Execution timed out 2085 ms 13220 KB Time limit exceeded
6 Execution timed out 2074 ms 12908 KB Time limit exceeded
7 Execution timed out 2076 ms 3600 KB Time limit exceeded
8 Execution timed out 2069 ms 1152 KB Time limit exceeded
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 Execution timed out 2074 ms 3220 KB Time limit exceeded
17 Execution timed out 2082 ms 1884 KB Time limit exceeded
18 Execution timed out 2067 ms 2048 KB Time limit exceeded
19 Execution timed out 2078 ms 1148 KB Time limit exceeded
20 Execution timed out 2017 ms 1048 KB Time limit exceeded