Submission #208344

#	Time	Username	Problem	Language	Result	Execution time	Memory
208344		arnold518	timeismoney (balkan11_timeismoney)	C++14	100 / 100	523 ms	632 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 200;
const int MAXM = 1e4;
const ll INF = 1e18;

struct Edge
{
	int u, v; ll x, y;
};

int N, M;
Edge E[MAXM+10];
pair<ll, pll> ans={INF, {0, 0}};

struct Point { ll x, y; };
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }
bool operator == (const Point &p, const Point &q) { return p.x==q.x && p.y==q.y; }

struct UF
{
	int par[MAXN+10];
	void init() { for(int i=0; i<=N; i++) par[i]=i; }
	int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
	void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }
} uf;

Point f(ll a, ll b, bool print)
{
	int i, j;

	Point r={0, 0};
	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q) { return p.x*b+p.y*a<q.x*b+q.y*a; });
	uf.init();

	for(i=1; i<=M; i++)
	{
		if(uf.Find(E[i].u)!=uf.Find(E[i].v))
		{
			if(print) printf("%d %d\n", E[i].u-1, E[i].v-1);
			uf.Union(E[i].u, E[i].v);
			r.x+=E[i].x;
			r.y+=E[i].y;
		}
	}
	return r;
}

void dnc(Point p, Point q)
{
	int i, j;
	if(p==q) return;

	ll a=q.x-p.x, b=p.y-q.y;
	Point r=f(a, b, 0);
	if(r.x*r.y<ans.first) ans={r.x*r.y, {a, b}};
	Point v1=p-r, v2=q-r;
	if(v1.x*v2.y-v1.y*v2.x==0) return;
	assert(v1.x*v2.y-v1.y*v2.x<0);
	dnc(p, r);
	dnc(r, q);
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++) scanf("%d%d%lld%lld", &E[i].u, &E[i].v, &E[i].x, &E[i].y), E[i].u++, E[i].v++;

	Point p=f(0, 1, 0), q=f(1, 0, 0);
	ans=min(ans, {p.x*p.y, {0, 1}});
	ans=min(ans, {q.x*q.y, {1, 0}});
	dnc(p, q);

	Point r=f(ans.second.first, ans.second.second, 0);
	printf("%lld %lld\n", r.x, r.y);
	f(ans.second.first, ans.second.second, 1);
}

Compilation message (stderr)

timeismoney.cpp: In function 'Point f(ll, ll, bool)':
timeismoney.cpp:35:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
timeismoney.cpp: In function 'void dnc(Point, Point)':
timeismoney.cpp:56:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
timeismoney.cpp:56:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:71:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
timeismoney.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
timeismoney.cpp:74:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d%lld%lld", &E[i].u, &E[i].v, &E[i].x, &E[i].y), E[i].u++, E[i].v++;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100