Submission #328245

#	Time	Username	Problem	Language	Result	Execution time	Memory
328245		Mackerel_Pike	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1012 ms	800 KiB

timeismoney

#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;

const int maxn = 255;
const int maxm = 10005;

int n, m;
int vis[maxm];

class Point{
public:
	int x, y;
	Point(){}
	Point(int x_, int y_): x(x_), y(y_){}
	inline bool operator == (const Point &oth)const{ return (x == oth.x && y == oth.y); }
	inline int operator * (const Point &oth)const{ return x * oth.x + y * oth.y; }
	inline Point operator * (const int &oth)const{ return Point(x * oth, y * oth); }
	inline Point& operator += (const Point &oth){ x += oth.x, y += oth.y; return *this; }
	inline Point& operator -= (const Point &oth){ x -= oth.x, y -= oth.y; return *this; }
	inline Point operator - (const Point &oth)const{ Point ret = *this; ret -= oth; return ret; }
};

class Edge{
public:
	int u, v;
	Point val;
	Edge(){}
	Edge(int u_, int v_, Point val_): u(u_), v(v_), val(val_){}
} ed[maxm];

class Dsu{
private:
	inline int find(int x){ return (x == fa[x]) ? x : (fa[x] = find(fa[x])); }
public:
	int fa[maxn];
	inline void init(){ FOR(i, 0, n) fa[i] = i; return; }
	inline bool merge(int x, int y){
		x = find(x), y = find(y);
		if(x == y)
			return false;
		fa[x] = y;
		return true;
	}
} dsu;

inline Point kruscal(Point w){
	vector<pii> vec;
	FOR(i, 0, m)
		vec.PB(MP(w * ed[i].val, i));
	sort(vec.begin(), vec.end());
	dsu.init();
	Point ret(0, 0);
	memset(vis, 0, sizeof(vis));
	FOR(i, 0, vec.size()){
		int id = vec[i].snd;
		ret += ed[id].val * (vis[id] = dsu.merge(ed[id].u, ed[id].v));
	}
	return ret;
}

inline Point solve(Point A, Point B){
//	printf("A = (%d %d) B = (%d %d)\n", A.x, A.y, B.x, B.y);
	Point W = A - B; swap(W.x, W.y); W.x = -W.x;
	Point C = kruscal(W);
	Point P = ((C == A || C == B) ? A : solve(A, C)), Q = ((C == A || C == B) ? B : solve(C, B));
	return (1ll * P.x * P.y < 1ll * Q.x * Q.y ? P : Q); 
}

int main(){
	scanf("%d%d", &n, &m);
	FOR(i, 0, m){
		int u, v, t, c; scanf("%d%d%d%d", &u, &v, &t, &c);
		ed[i] = Edge(u, v, Point(t, c));	
	}
	
	Point A = kruscal(Point(0, 1));
	Point B = kruscal(Point(1, 0));
	
	Point C = solve(A, B);
	
	kruscal(Point(C.y, C.x));
	
	printf("%d %d\n", C.x, C.y);
	FOR(i, 0, m) if(vis[i])
		printf("%d %d\n", ed[i].u, ed[i].v);
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'Point kruscal(Point)':
timeismoney.cpp:5:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
timeismoney.cpp:68:2: note: in expansion of macro 'FOR'
   68 |  FOR(i, 0, vec.size()){
      |  ^~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
timeismoney.cpp:86:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   int u, v, t, c; scanf("%d%d%d%d", &u, &v, &t, &c);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100