Submission #580626

# Submission time Handle Problem Language Result Execution time Memory
580626 2022-06-21T14:39:47 Z Lobo timeismoney (balkan11_timeismoney) C++17
0 / 100
2000 ms 1572 KB
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 220;

int n, m, ds[maxn], dsz[maxn];
pair<int,pair<int,int>> ans;
vector<pair<pair<int,int>,pair<int,int>>> edg;
vector<pair<int,int>> ansv;

int find(int u) {
    if(u == ds[u]) return u;
    return ds[u] = find(ds[u]);
}

void join(int u, int v) {
    if(dsz[u] < dsz[v]) swap(u,v);
    dsz[u]+= dsz[v];
    ds[v] = u;
}

pair<int,int> mst(dbl c1, dbl t1) {
    priority_queue<pair<dbl,int>, vector<pair<dbl,int>>, greater<pair<dbl,int>>> pq;
    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        dsz[i] = 1;
    }
    for(int i = 0; i < edg.size(); i++) {
        int c = edg[i].sc.fr;
        int t = edg[i].sc.sc;
        pq.push(mp(c*c1+t*t1,i));
    }
    int C = 0;
    int T = 0;
    vector<pair<int,int>> curv;
    while(pq.size()) {
        int id = pq.top().sc;
        pq.pop();
        int u = find(edg[id].fr.fr);
        int v = find(edg[id].fr.sc);
        int c = edg[id].sc.fr;
        int t = edg[id].sc.sc;

        if(u != v) {
            join(u,v);
            curv.pb(mp(edg[id].fr.fr,edg[id].fr.sc));
            C+= c;
            T+= t;
        }
    }

    if(ans.fr > C*T) {
        ans.fr = C*T;
        ans.sc = mp(C,T);
        ansv = curv;
    }
    // cout << " " << c1 << " " << t1 << " " << C << " " << T << endl;
    return mp(C,T);
}

void dec(int cl, int tl, int cr, int tr) {
    // cout << cl << " " << tl << " " << cr << " " << tr << endl;
    int dc = cr-cl; // > 0
    int dt = tr-tl; // < 0
    dbl sz = sqrt(dc*dc + dt*dt);
    auto aux = mst(dt/sz,-dc/sz);
    int c = aux.fr;
    int t = aux.sc;
    if(c == cl || c == cr) return;
    dec(cl,tl,c,t);
    dec(c,t,cr,tr);
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u,v,c,t; cin >> u >> v >> c >> t;
        u++;
        v++;
        edg.pb(mp(mp(u,v),mp(c,t)));
    }

    ans.fr = inf;
    pair<int,int> aux;
    aux = mst(0,1);
    int c0 = aux.fr;
    int t0 = aux.sc;
    aux = mst(1,0);
    int c1 = aux.fr;
    int t1 = aux.sc;
    dec(c0,t0,c1,t1);

    cout << ans.sc.fr << " " << ans.sc.sc << endl;
    for(auto x : ansv) {
        cout << x.fr-1 << " " << x.sc-1 << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

timeismoney.cpp: In function 'std::pair<int, int> mst(long double, long double)':
timeismoney.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < edg.size(); i++) {
      |                    ~~^~~~~~~~~~~~
timeismoney.cpp: In function 'void solve()':
timeismoney.cpp:95:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000010' to '-1486618614' [-Woverflow]
   95 |     ans.fr = inf;
      |              ^~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 3 ms 468 KB Output isn't correct
8 Incorrect 12 ms 1300 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Incorrect 13 ms 376 KB Output isn't correct
15 Incorrect 8 ms 340 KB Output isn't correct
16 Execution timed out 2055 ms 1008 KB Time limit exceeded
17 Execution timed out 2080 ms 960 KB Time limit exceeded
18 Execution timed out 2098 ms 880 KB Time limit exceeded
19 Execution timed out 2092 ms 1572 KB Time limit exceeded
20 Execution timed out 2080 ms 1564 KB Time limit exceeded