#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 501;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 8;
ll n;
struct edge {
ll x, y, t, c;
};
ll parent[NMAX], cnt[NMAX];
ll root(ll x) {
if(x == parent[x]) {
return x;
}
return parent[x] = root(parent[x]);
}
ll cost, timp;
vector <edge> fol;
void init(ll n) {
cost = timp = 0;
fol.clear();
for(ll i = 1; i <= n; i++) {
parent[i] = i;
cnt[i] = 1;
}
}
void merge(edge x) {
ll a = root(x.x);
ll b = root(x.y);
if(a == b)
return;
if(cnt[a] < cnt[b])
swap(a, b);
cnt[a] += cnt[b];
cnt[b] = 0;
parent[b] = a;
cost += x.c;
timp += x.t;
fol.push_back(x);
}
ll dx, dy;
pii best;
ll minim = (1LL << 60);
ll _prll;
bool cmp(edge a, edge b) {
return a.t * dx + a.c * dy < b.t * dx + b.c * dy;
}
vector <edge> edges;
ll OK(pii a, pii b, pii c) {
return (a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) <= 0);
}
pii MST() {
sort(edges.begin(), edges.end(), cmp);
init(n);
for(auto x : edges) {
merge(x);
}
if(!_prll)
return {cost, timp};
cout << timp << " " << cost << "\n";
for(auto x : fol) {
cout << x.x - 1 << " " << x.y - 1 << "\n";
}
return {cost, timp};
}
void Solve(pii A, pii B) {
dx = B.first - A.first;
dy = A.second - B.second;
pii C = MST();
// debug(C.first);
// debug(C.second);
if(OK(A, B, C)) {
return;
}
if(C.first * C.second < minim) {
minim = C.first * C.second;
best = {dx, dy};
}
Solve(A, C);
Solve(C, B);
}
int main() {
//ifstream cin("grarbore.in");
//ofstream cout("grarbore.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m;
cin >> n >> m;
for(ll i = 1; i <= m; i++) {
edge x;
cin >> x.x >> x.y >> x.t >> x.c;
x.x++;
x.y++;
edges.push_back(x);
}
dx = 0;
dy = 1;
pii A = MST();
dx = 1;
dy = 0;
pii B = MST();
Solve(A, B);
_prll = 1;
dx = best.first;
dy = best.second;
MST();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
464 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
1104 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 19 |
Incorrect |
10 ms |
1104 KB |
Output isn't correct |
| 20 |
Incorrect |
10 ms |
1104 KB |
Output isn't correct |
