oj.uz

Submission #208338

# Submission time Handle Problem Language Result Execution time Memory
208338 2020-03-10T19:35:11 Z arnold518 timeismoney (balkan11_timeismoney) C++14
40 / 100
 2000 ms 65540 KB 
#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, 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);
	ans=min(ans, {r.x*r.y, {a, b}});
	Point v1=p-r, v2=q-r;
	//if(v1.x*v2.y==v1.y*v2.x) return;
	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%d%d", &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

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:62:8: warning: variable 'v1' set but not used [-Wunused-but-set-variable]
  Point v1=p-r, v2=q-r;
        ^~
timeismoney.cpp:62:16: warning: variable 'v2' set but not used [-Wunused-but-set-variable]
  Point v1=p-r, v2=q-r;
                ^~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:70:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
timeismoney.cpp:72: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:73:85: 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%d%d", &E[i].u, &E[i].v, &E[i].x, &E[i].y), E[i].u++, E[i].v++;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 10 ms 656 KB Output is correct
9 Runtime error 331 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 763 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 551 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 1778 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1799 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Execution timed out 2072 ms 14384 KB Time limit exceeded
15 Execution timed out 2059 ms 16284 KB Time limit exceeded
16 Execution timed out 2039 ms 1668 KB Time limit exceeded
17 Execution timed out 2033 ms 1716 KB Time limit exceeded
18 Execution timed out 2059 ms 1960 KB Time limit exceeded
19 Execution timed out 2067 ms 1144 KB Time limit exceeded
20 Execution timed out 2078 ms 972 KB Time limit exceeded