oj.uz

Submission #446112

# Submission time Handle Problem Language Result Execution time Memory
446112 2021-07-21T00:33:39 Z Evirir timeismoney (balkan11_timeismoney) C++17
100 / 100
 1094 ms 2024 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 205;
const int MAXM = 10005;

struct DSU
{
	struct Node{ int p, sz; };
	int cc;
	vector<Node> dsu;
	DSU(int n){
		dsu.resize(n); cc=n;
		forn(i,0,n){ dsu[i]={i,1}; }
	}
	int rt(int u){ return (dsu[u].p==u) ? u : dsu[u].p=rt(dsu[u].p); }
	bool sameset(int u, int v){ return rt(u)==rt(v); }
	void merge(int u, int v)
	{
		u=rt(u); v=rt(v);
		if(u==v) return;
		if(dsu[u].sz<dsu[v].sz) swap(u,v);
		dsu[u].sz+=dsu[v].sz;
		dsu[v].p=dsu[u].p;
		cc--;
	}
};

struct Edge
{
	int u,v;
	ll x,y;
	int id;
	bool operator<(const Edge& e){ return x+y < e.x+e.y; }
};

int n,m;
vector<Edge> edges;
vector<ii> bestedges;
ii best={3e9,3e9};
ll besta,bestb;

ii solve(ll a, ll b, bool fin=false)
{
	vector<Edge> ve;
	for(Edge e: edges)
	{
		ve.pb({e.u, e.v, a*e.x, b*e.y, e.id});
	}
	sort(ve.begin(), ve.end());
	
	DSU dsu(n);
	ll sumx=0,sumy=0;
	for(Edge e: ve)
	{
		if(dsu.cc==1) break;
		int u=e.u, v=e.v;
		if(dsu.sameset(u,v)) continue;
		dsu.merge(u,v);
		sumx+=edges[e.id].x;
		sumy+=edges[e.id].y;
		if(fin) bestedges.pb({u,v});
	}
	ii res=ii(sumx, sumy);
	if(res.F*res.S < best.F*best.S)
	{
		best=res;
		besta=a;
		bestb=b;
	}
	return res;
}

bool good(ii a, ii b, ii c)
{
	return (c.S-b.S)*(b.F-a.F)>(b.S-a.S)*(c.F-b.F);
}

void rec(ii a, ii b)
{
	ii res=solve(a.S-b.S, b.F-a.F);
	if(good(a,res,b))
	{
		rec(a,res);
		rec(res,b);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m;
	forn(i,0,m)
	{
		int u,v,x,y; cin>>u>>v>>x>>y;
		edges.pb(Edge{u,v,x,y,i});
	}
	
	ii minx=solve(1,0);
	ii miny=solve(0,1);
	
	rec(minx, miny);
	solve(besta, bestb, true);
	
	cout<<best.F<<" "<<best.S<<'\n';
	for(auto e: bestedges) cout<<e.F<<" "<<e.S<<'\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 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 444 KB Output is correct
8 Correct 8 ms 1572 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 7 ms 312 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 100 ms 512 KB Output is correct
17 Correct 106 ms 516 KB Output is correct
18 Correct 101 ms 508 KB Output is correct
19 Correct 1072 ms 2024 KB Output is correct
20 Correct 1094 ms 1724 KB Output is correct