oj.uz

Submission #392572

# Submission time Handle Problem Language Result Execution time Memory
392572 2021-04-21T10:40:57 Z Vladth11 timeismoney (balkan11_timeismoney) C++14
0 / 100
 773 ms 716 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";
    }
  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;
    }
    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;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Integer 200 violates the range [0, 199]
2 Incorrect 1 ms 204 KB Integer 10 violates the range [0, 9]
3 Incorrect 1 ms 204 KB Integer 20 violates the range [0, 19]
4 Incorrect 1 ms 208 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 460 KB Output isn't correct
7 Incorrect 2 ms 332 KB Output isn't correct
8 Incorrect 6 ms 716 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Incorrect 1 ms 204 KB Output isn't correct
11 Incorrect 1 ms 204 KB Integer 20 violates the range [0, 19]
12 Incorrect 1 ms 204 KB Integer 50 violates the range [0, 49]
13 Incorrect 1 ms 204 KB Integer 50 violates the range [0, 49]
14 Incorrect 6 ms 332 KB Integer 100 violates the range [0, 99]
15 Incorrect 4 ms 332 KB Integer 200 violates the range [0, 199]
16 Incorrect 85 ms 360 KB Integer 200 violates the range [0, 199]
17 Incorrect 90 ms 368 KB Integer 200 violates the range [0, 199]
18 Incorrect 83 ms 332 KB Integer 200 violates the range [0, 199]
19 Incorrect 730 ms 716 KB Integer 200 violates the range [0, 199]
20 Incorrect 773 ms 716 KB Integer 200 violates the range [0, 199]