oj.uz

Submission #937038

# Submission time Handle Problem Language Result Execution time Memory
937038 2024-03-03T09:18:43 Z Khalid_Alabdullatif timeismoney (balkan11_timeismoney) C++14
100 / 100
 357 ms 736 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<ll,int>
using namespace std;
const int N=1e4+7;
struct point{
    point(){}
    point(ll xx, ll yy):x(xx),y(yy){}
    ll x=0,y=0;
    friend point operator+(point a,point b){
        return point(a.x+b.x,b.y+b.y);
    }
    friend point operator-(point a,point b){
        return point(a.x-b.x,a.y-b.y);
    }
    friend ll operator^(point a, point b){
        return a.x*b.y-a.y*b.x;
    }
    friend ll operator*(point a,point b){
        return a.x*b.x+a.y*b.y;
    }
    friend bool operator<(point a,point b){
        if(a.x<b.x)
            return 1;
        if(a.x==b.x){
            if(a.y<=b.y)
                return 1;
            return 0;
        }
        return 0;
    }
    friend bool operator>(point a,point b){
        if(a.x>b.x)
            return 1;
        if(a.x==b.x){
            if(a.y>=b.y)
                return 1;
            return 0;
        }
        return 0;
    }
};
struct edge{
    int v,u,t,c;
};
int n,m;
int par[201],sz[201];
point sol(1e18,1e18),ans;
bool ok[201];
edge e[N];
int get(int x){
    if(x==par[x])
        return x;
    return par[x]=get(par[x]);
}
bool merge(int a,int b){
    a=get(a),b=get(b);
    if(a==b)
        return 0;
    if(sz[a]>sz[b])
        swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];
    return 1;
}
void init(){
    for(int i=0;i<n;i++)
        par[i]=i,sz[i]=1;
}
point mst(point x){
    sort(e,e+m,[&](edge e1,edge e2){
        return (x.x*e1.t + x.y*e1.c)<(x.x*e2.t + x.y*e2.c);
    });
    init();
    point an2st;
    for(int i=0;i<m;i++)
        if(merge(e[i].v,e[i].u))
            an2st.x+=e[i].t,an2st.y+=e[i].c;
    return an2st;
}
void solve(point a,point b){
    point x=b-a;
    point dir=point(-x.y,x.x);
    point an2st=mst(dir);
    if(an2st.x*an2st.y<sol.x*sol.y){
        sol=an2st;
        ans=dir;
    }
    if (((x)^(an2st-a))==0) return;
    solve(a,an2st);
    solve(an2st,b);
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>e[i].v>>e[i].u>>e[i].t>>e[i].c;

    point a=mst(point(1, 0));
    sol=a;
    ans=point(1, 0);
    
    point b=mst(point(0, 1));
    if (b.x*b.y < sol.x * sol.y){
        sol=b;
        ans=point(0, 1);
    }
    solve(a,b);
    mst(ans);
    cout<<sol.x<<' '<<sol.y<<endl;
    init();
    for(int i=0;i<m;i++)
        if(merge(e[i].v,e[i].u))
            cout<<e[i].v<<' '<<e[i].u<<endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 476 KB Output is correct
15 Correct 3 ms 360 KB Output is correct
16 Correct 42 ms 348 KB Output is correct
17 Correct 43 ms 348 KB Output is correct
18 Correct 40 ms 348 KB Output is correct
19 Correct 349 ms 600 KB Output is correct
20 Correct 357 ms 736 KB Output is correct