oj.uz

Submission #392564

# Submission time Handle Problem Language Result Execution time Memory
392564 2021-04-21T10:35:45 Z Vladth11 timeismoney (balkan11_timeismoney) C++14
0 / 100
 786 ms 1104 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 = 501;
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[NMAX], cnt[NMAX];
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 3 ms 460 KB Execution killed with signal 11
2 Runtime error 3 ms 460 KB Execution killed with signal 11
3 Runtime error 2 ms 460 KB Execution killed with signal 11
4 Runtime error 3 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 8 ms 1104 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 7 ms 460 KB Execution killed with signal 11
15 Runtime error 6 ms 460 KB Execution killed with signal 11
16 Runtime error 89 ms 504 KB Execution killed with signal 11
17 Runtime error 96 ms 504 KB Execution killed with signal 11
18 Runtime error 90 ms 492 KB Execution killed with signal 11
19 Runtime error 786 ms 992 KB Execution killed with signal 11
20 Runtime error 775 ms 984 KB Execution killed with signal 11