oj.uz

Submission #392560

# Submission time Handle Problem Language Result Execution time Memory
392560 2021-04-21T10:31:18 Z Vladth11 timeismoney (balkan11_timeismoney) C++14
0 / 100
 795 ms 1004 KB 
#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 = 201;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 8;

int n;

struct edge {
    int x, y, t, c;
};

int parent[201], cnt[201];
int root(int x) {
    if(x == parent[x]) {
        return x;
    }
    return parent[x] = root(parent[x]);
}
int cost, timp;
vector <edge> fol;
void init(int n) {
    cost = timp = 0;
    fol.clear();
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
        cnt[i] = 0;
    }
}
void merge(edge x) {
    int a = root(x.x);
    int 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);
}


int dx, dy;
pii best;
int minim = 2e9;
int _print;

bool cmp(edge a, edge b) {
    return a.t * dx + a.c * dy < b.t * dx + b.c * dy;
}

vector <edge> edges;

int 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(!_print)
        return {cost, timp};
    cout << timp << " " << cost << "\n";
    for(auto x : fol) {
        cout << x.x << " " << x.y << "\n";
    }
}

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;
    }
    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);
    int m;
    cin >> n >> m;
    for(int 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);
    _print = 1;
    dx = best.first;
    dy = best.second;
    MST();
    return 0;
}

Compilation message

timeismoney.cpp: In function 'pii MST()':
timeismoney.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 11
2 Runtime error 2 ms 460 KB Execution killed with signal 11
3 Runtime error 2 ms 460 KB Execution killed with signal 11
4 Runtime error 2 ms 460 KB Execution killed with signal 11
5 Runtime error 2 ms 460 KB Execution killed with signal 11
6 Runtime error 2 ms 460 KB Execution killed with signal 11
7 Runtime error 3 ms 588 KB Execution killed with signal 11
8 Runtime error 9 ms 1004 KB Execution killed with signal 11
9 Runtime error 2 ms 460 KB Execution killed with signal 11
10 Runtime error 2 ms 460 KB Execution killed with signal 11
11 Runtime error 2 ms 460 KB Execution killed with signal 11
12 Runtime error 2 ms 460 KB Execution killed with signal 11
13 Runtime error 2 ms 460 KB Execution killed with signal 11
14 Runtime error 8 ms 460 KB Execution killed with signal 11
15 Runtime error 6 ms 484 KB Execution killed with signal 11
16 Runtime error 91 ms 488 KB Execution killed with signal 11
17 Runtime error 102 ms 496 KB Execution killed with signal 11
18 Runtime error 91 ms 496 KB Execution killed with signal 11
19 Runtime error 795 ms 988 KB Execution killed with signal 11
20 Runtime error 773 ms 1004 KB Execution killed with signal 11