oj.uz

답안 #376650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376650 2021-03-11T23:47:07 Z jeroenodb 시간이 돈 (balkan11_timeismoney) C++14
0 / 100
 433 ms 668 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 200+1, mxM=1e4, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
struct DSU{
    vector<int> sz,parent;
    int components;
    DSU(int n) {
        sz.assign(n,1);
        components = n;
        parent.resize(n);
        for(int i=0;i<n;++i) parent[i]=i;
    }
    void link(int a, int b) {
        components--;
        if(sz[a]<sz[b]) {
            swap(a,b);
        }
        sz[a] = max(sz[a],sz[b]+1);
        parent[b] = a;
    }
    void unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) link(pa,pb);
    }
    int find(int a) {
        if(a==parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
};
ll ft,fc;
struct edge{
    int a,b,t,c;
    bool operator<(const edge& o) const {
        return ft*t+fc*c < ft*o.t+fc*o.c;
    }
};
int n,m; 
edge edges[mxM];
pt kruskal() {
    DSU dsu(n);
    sort(edges,edges+m);
    pt ans = 0;
    for(int j=0;j<m;++j) {
        auto& e = edges[j];
        int pa = dsu.find(e.a), pb=dsu.find(e.b);
        if(pa!=pb) {
            ans+=pt{e.t,e.c};
            dsu.link(pa,pb);
        }
        if(dsu.components==1) break;
    }
    return ans;
}
int bestfc=0, bestft=1, best=oo;
void solve(pt ul, pt rd) {
    ft = ul.Y-rd.Y;
    fc = rd.X-ul.X;
    auto nw = kruskal();
    int ans = nw.X*nw.Y;
    if(ans<best) {
        best = ans;
        bestfc = fc;
        bestft = ft;
    }
    if(ccw(ul,rd,nw)==0) return;
    solve(ul,nw), solve(nw,rd);
}
int main() {
    cin >> n>>m;
    for(int i=0;i<m;++i) {
        int a,b,t,c; cin >> a >> b >> t >> c;
        edges[i] = {a,b,t,c};
    }
    ft = 1, fc = 0;
    auto p1 = kruskal();
    ft = 0, fc = 1;
    auto p2 = kruskal();
    solve(p1,p2);
    cout << bestft << ' ' << bestfc << '\n';
    ft = bestft;
    fc = bestfc;
    DSU dsu(n);
    sort(edges,edges+m);
    pt ans = 0;
    for(int j=0;j<m;++j) {
        auto& e = edges[j];
        int pa = dsu.find(e.a), pb=dsu.find(e.b);
        if(pa!=pb) {
            ans+=pt{e.t,e.c};
            dsu.link(pa,pb);
            cout << e.a << ' ' << e.b << '\n';
        }
        if(dsu.components==1) break;
    }

}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 3 ms 512 KB Output isn't correct
8 Incorrect 11 ms 492 KB Output isn't correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Incorrect 1 ms 364 KB Output isn't correct
14 Incorrect 4 ms 364 KB Output isn't correct
15 Incorrect 3 ms 364 KB Output isn't correct
16 Incorrect 50 ms 364 KB Output isn't correct
17 Incorrect 55 ms 364 KB Output isn't correct
18 Incorrect 50 ms 364 KB Output isn't correct
19 Incorrect 431 ms 512 KB Output isn't correct
20 Incorrect 433 ms 668 KB Output isn't correct