oj.uz

Submission #392570

# Submission time Handle Problem Language Result Execution time Memory
392570 2021-04-21T10:38:15 Z Vladth11 timeismoney (balkan11_timeismoney) C++14
0 / 100
 764 ms 1044 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] = 1;
    }
}
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 8 ms 1044 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 464 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 5 ms 460 KB Execution killed with signal 11
16 Runtime error 87 ms 504 KB Execution killed with signal 11
17 Runtime error 90 ms 624 KB Execution killed with signal 11
18 Runtime error 86 ms 580 KB Execution killed with signal 11
19 Runtime error 747 ms 996 KB Execution killed with signal 11
20 Runtime error 764 ms 988 KB Execution killed with signal 11