oj.uz

답안 #580709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580709 2022-06-21T17:10:17 Z Lobo 시간이 돈 (balkan11_timeismoney) C++17
35 / 100
 2000 ms 1604 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;
            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++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
35.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 340 KB Time limit exceeded
2 Execution timed out 2079 ms 212 KB Time limit exceeded
3 Execution timed out 2078 ms 212 KB Time limit exceeded
4 Execution timed out 2078 ms 212 KB Time limit exceeded
5 Execution timed out 2048 ms 340 KB Time limit exceeded
6 Execution timed out 2063 ms 340 KB Time limit exceeded
7 Execution timed out 2080 ms 468 KB Time limit exceeded
8 Execution timed out 2089 ms 984 KB Time limit exceeded
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 19 ms 368 KB Output is correct
15 Correct 29 ms 364 KB Output is correct
16 Execution timed out 2076 ms 468 KB Time limit exceeded
17 Execution timed out 2075 ms 476 KB Time limit exceeded
18 Execution timed out 2074 ms 864 KB Time limit exceeded
19 Execution timed out 2077 ms 1604 KB Time limit exceeded
20 Execution timed out 2083 ms 1064 KB Time limit exceeded