답안 #580719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580719 2022-06-21T17:17:54 Z Lobo 시간이 돈 (balkan11_timeismoney) C++17
35 / 100
2000 ms 1224 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 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;
    
    vector<pair<dbl,int>> edgs[maxn];
    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 u = edg[i].fr.fr;
        int v = edg[i].fr.sc;
        edgs[u].pb(mp(c*c1+t*t1,i));
        edgs[v].pb(mp(c*c1+t*t1,i));
    }
    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        dsz[i] = 1;
        sort(all(edgs[i]),greater<pair<dbl,int>>());
    }

    int C = 0;
    int T = 0;
    vector<pair<int,int>> curv;
    while((int) curv.size() != n-1) {
        pair<dbl,int> cur = mp(inf1,0);
        for(int i = 1; i <= n; i++) {
            if(edgs[i].size() == 0) continue;
            int u1 = find(edg[edgs[i].back().sc].fr.fr);
            int v1 = find(edg[edgs[i].back().sc].fr.sc);
            if(u1 == v1) {
                edgs[i].pop_back();
                continue;
            }
            cur = min(cur,edgs[i].back());
        }

        int id = cur.sc;
        int u = edg[id].fr.fr;
        int v = edg[id].fr.sc;
        if(edgs[u].size() && edgs[u].back() == cur) edgs[u].pop_back();
        if(edgs[v].size() && edgs[v].back() == cur) edgs[v].pop_back();
        u = find(u);
        v = find(v);
        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);
        swap(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 = inf1;
    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(double, double)':
timeismoney.cpp:37: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]
   37 |     for(int i = 0; i < edg.size(); i++) {
      |                    ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 340 KB Time limit exceeded
2 Execution timed out 2080 ms 212 KB Time limit exceeded
3 Execution timed out 2047 ms 212 KB Time limit exceeded
4 Execution timed out 2084 ms 212 KB Time limit exceeded
5 Execution timed out 2079 ms 340 KB Time limit exceeded
6 Execution timed out 2082 ms 340 KB Time limit exceeded
7 Execution timed out 2079 ms 468 KB Time limit exceeded
8 Execution timed out 2077 ms 992 KB Time limit exceeded
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 2 ms 212 KB Output is correct
14 Correct 30 ms 340 KB Output is correct
15 Correct 60 ms 360 KB Output is correct
16 Execution timed out 2080 ms 468 KB Time limit exceeded
17 Execution timed out 2059 ms 480 KB Time limit exceeded
18 Execution timed out 2084 ms 828 KB Time limit exceeded
19 Execution timed out 2086 ms 1224 KB Time limit exceeded
20 Execution timed out 2077 ms 1068 KB Time limit exceeded