Submission #392619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392619	2021-04-21T11:16:09 Z	Vladth11	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1247 ms	976 KB

timeismoney

#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(cost * timp < minim) {
        minim = cost * timp;
        best = {dx, dy};
    }
    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, C, B)) {
        return;
    }

    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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 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	3 ms	332 KB	Output is correct
8	Correct	8 ms	976 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	8 ms	332 KB	Output is correct
15	Correct	5 ms	332 KB	Output is correct
16	Correct	134 ms	432 KB	Output is correct
17	Correct	142 ms	436 KB	Output is correct
18	Correct	147 ms	428 KB	Output is correct
19	Correct	1243 ms	976 KB	Output is correct
20	Correct	1247 ms	976 KB	Output is correct