oj.uz

Submission #392577

# Submission time Handle Problem Language Result Execution time Memory
392577 2021-04-21T10:45:06 Z Vladth11 timeismoney (balkan11_timeismoney) C++14
0 / 100
 788 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 1LL * a.t * dx + 1LL *  a.c * dy < 1LL * b.t * dx + 1LL * 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 - 1 << " " << x.y - 1 << "\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 3 ms 460 KB Execution killed with signal 11
7 Runtime error 3 ms 508 KB Execution killed with signal 11
8 Runtime error 8 ms 1104 KB Execution killed with signal 11
9 Runtime error 2 ms 464 KB Execution killed with signal 11
10 Runtime error 3 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 452 KB Execution killed with signal 11
14 Runtime error 8 ms 460 KB Execution killed with signal 11
15 Runtime error 6 ms 460 KB Execution killed with signal 11
16 Runtime error 96 ms 500 KB Execution killed with signal 11
17 Runtime error 95 ms 504 KB Execution killed with signal 11
18 Runtime error 87 ms 496 KB Execution killed with signal 11
19 Runtime error 772 ms 1000 KB Execution killed with signal 11
20 Runtime error 788 ms 1096 KB Execution killed with signal 11