Submission #580623

# Submission time Handle Problem Language Result Execution time Memory
580623 2022-06-21T14:38:33 Z Lobo timeismoney (balkan11_timeismoney) C++17
75 / 100
2000 ms 1920 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<long long int, long long int> mst(long double, long double)':
timeismoney.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < edg.size(); i++) {
      |                    ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 14 ms 1640 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 17 ms 340 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Execution timed out 2070 ms 1028 KB Time limit exceeded
17 Execution timed out 2077 ms 1008 KB Time limit exceeded
18 Execution timed out 2084 ms 940 KB Time limit exceeded
19 Execution timed out 2078 ms 1812 KB Time limit exceeded
20 Execution timed out 2075 ms 1920 KB Time limit exceeded