답안 #634148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634148 2022-08-23T22:15:22 Z Mazza 시간이 돈 (balkan11_timeismoney) C++14
0 / 100
2000 ms 65536 KB
#pragma GCC optimize("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vvp vector<vector<pi>>

    int n,m;
struct edge{
    int a,b,t,c,idx;
};
vector<edge> edges;
vector<int> weight;
pi sol;
vector<pi> mstsol;
vector<pi> currmst;
struct dsu{

    vi par,size;
    int find(int i){
        return par[i] == i ? i : par[i] = find(par[i]);
    }
    void uni(int a, int b){
        a = find(a); b = find(b);
        if(a == b) return;
        if(size[a] < size[b]) swap(a,b);
        size[a] += size[b];
        par[b] = a;
    }
    dsu(int n){
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        size.resize(n,1);
    }
};
pi solve(){
    sort(edges.begin(), edges.end(), [&](const edge &a, const edge &b){
        return weight[a.idx] < weight[b.idx];
    });

    dsu d(n);
    int tcost = 0, ccost = 0;
    currmst.clear();
    for(int i = 0; i < m; i++){
        edge &a = edges[i];
        if(d.find(a.a) != d.find(a.b)){
            tcost += a.t; ccost += a.c;
            d.uni(a.a, a.b);
            currmst.pb({a.a, a.b});
        }
    }

    return {tcost, ccost};
}
pi sub(pi a, pi b){
    return {a.first - b.first, a.second - b.second};
}
bool sopra(pi a, pi b){
    return (a.first * b.second - a.second * b.first > 0);
}
int main()
{
    cin.tie(0); cin.sync_with_stdio(0);cout.tie(0); cout.sync_with_stdio(0);
    cin>>n>>m;
    edges.resize(m); weight.resize(m);
    for(int i = 0; i < m; i++){
        edge a;
        cin>>a.a>>a.b>>a.t>>a.c;
        a.idx = i;
        edges[i] = a;
    }
    
    //soluzione ottimale per t
    for(int i = 0; i < m; i++){
        int idx = edges[i].idx;
        weight[idx] = edges[i].t;
    }
    pi a = solve();
    pi best = a;
    mstsol = currmst;

    //soluzione ottimale per c
    for(int i = 0; i < m; i++){
        int idx = edges[i].idx;
        weight[idx] = edges[i].c;
    }

    pi b = solve();
    //swap a e b se b best
    //area triangolo negativa quindi minimizzo per la migliore
    if((ll)best.first * best.second > (ll)b.first * b.second){
        best = b;
        mstsol = currmst;
        swap(a,b);
    }

    stack<pair<pi,pi>> s; s.push({a,b});
    while(!s.empty()){
        //change wwight
        a = s.top().first, b = s.top().second;
        s.pop();
        for(int i = 0; i < m; i++){
            int idx = edges[i].idx;
            weight[idx] = edges[i].c * (b.first - a.first) - edges[i].t * (b.second - a.second);
        }
        //run mst
        pi p = solve();
        //sopra retta a-b, punto peggiore
        if(sopra(sub(b,a), sub(p,a)) ){
            continue;
        }

        if((ll)best.first * best.second > (ll)p.first * p.second){
            best = p;
            mstsol = currmst;
        }

        s.push({a,p});
        s.push({p,b});
    }

    cout << best.first << " " << best.second << "\n";
    for(pi &a:mstsol){
        cout << a.first << " " << a.second << "\n";
    }

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2085 ms 5512 KB Time limit exceeded
2 Runtime error 1857 ms 65536 KB Execution killed with signal 9
3 Execution timed out 2082 ms 47680 KB Time limit exceeded
4 Execution timed out 2089 ms 14924 KB Time limit exceeded
5 Execution timed out 2084 ms 3744 KB Time limit exceeded
6 Execution timed out 2089 ms 3576 KB Time limit exceeded
7 Execution timed out 2093 ms 1000 KB Time limit exceeded
8 Execution timed out 2079 ms 944 KB Time limit exceeded
9 Runtime error 1932 ms 65536 KB Execution killed with signal 9
10 Execution timed out 2089 ms 30792 KB Time limit exceeded
11 Execution timed out 2089 ms 48308 KB Time limit exceeded
12 Execution timed out 2092 ms 16252 KB Time limit exceeded
13 Execution timed out 2092 ms 16252 KB Time limit exceeded
14 Execution timed out 2084 ms 3668 KB Time limit exceeded
15 Execution timed out 2085 ms 2920 KB Time limit exceeded
16 Execution timed out 2086 ms 716 KB Time limit exceeded
17 Execution timed out 2090 ms 828 KB Time limit exceeded
18 Execution timed out 2084 ms 616 KB Time limit exceeded
19 Execution timed out 2095 ms 556 KB Time limit exceeded
20 Execution timed out 2080 ms 700 KB Time limit exceeded