oj.uz

Submission #1029158

# Submission time Handle Problem Language Result Execution time Memory
1029158 2024-07-20T13:12:48 Z lucri timeismoney (balkan11_timeismoney) C++17
5 / 100
 578 ms 1128 KB 
#include <bits/stdc++.h>
using namespace std;
long long t[210],u[10010],v[10010],ti[10010],mo[10010],n,m,vmax=2000000000,st,sm,p1,p2;
long long sumt,summ;
struct muchii{long long u,v,val,valt,valm;}a[100010];
long long tata(long long n)
{
    if(t[n]==n)return n;
    return t[n]=tata(t[n]);
}
bool comp(muchii a,muchii b)
{
    if(a.val!=b.val)return a.val<b.val;
    if(a.u!=b.u)return a.u<b.u;
    if(a.v!=b.v)return a.v<b.v;
    return a.valt<b.valm;
}
void calculeaza(long long v1,long long v2)
{
    for(long long i=0;i<n;++i)
        t[i]=i;
    for(long long i=1;i<=m;++i)
        a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]};
    sumt=summ=0;
    sort(a+1,a+m+1,comp);
    for(long long i=1;i<=m;++i)
    {
        if(tata(a[i].u)!=tata(a[i].v))
        {
            t[a[i].u]=a[i].v;
            sumt+=a[i].valt;
            summ+=a[i].valm;
        }
    }
}
void scrie(long long v1,long long v2)
{
    for(long long i=0;i<n;++i)
        t[i]=i;
    for(long long i=1;i<=m;++i)
        a[i]={u[i],v[i],ti[i]*v1+mo[i]*v2,ti[i],mo[i]};
    sort(a+1,a+m+1,comp);
    for(long long i=1;i<=m;++i)
    {
        if(tata(a[i].u)!=tata(a[i].v))
        {
            t[a[i].u]=a[i].v;
            cout<<a[i].u<<' '<<a[i].v<<'\n';
        }
    }
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=m;++i)
        cin>>u[i]>>v[i]>>ti[i]>>mo[i];
    for(long long i=0;i<=260;++i)
    {
        calculeaza(i,260);
        if(sumt*summ<vmax)
        {
            st=sumt,sm=summ;
            vmax=sumt*summ;
            p1=i;
            p2=260;
        }
        calculeaza(260,i);
        if(sumt*summ<vmax)
        {
            st=sumt,sm=summ;
            vmax=sumt*summ;
            p1=260;
            p2=i;
        }
    }
    cout<<st<<' '<<sm<<'\n';
    scrie(p1,p2);
    return 0;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 476 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 444 KB Output isn't correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Incorrect 12 ms 540 KB Output isn't correct
6 Incorrect 8 ms 348 KB Output isn't correct
7 Incorrect 73 ms 604 KB Output isn't correct
8 Incorrect 578 ms 1116 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 448 KB Output isn't correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Incorrect 2 ms 348 KB Output isn't correct
13 Incorrect 2 ms 348 KB Output isn't correct
14 Incorrect 17 ms 348 KB Output isn't correct
15 Incorrect 12 ms 452 KB Output isn't correct
16 Incorrect 109 ms 604 KB Output isn't correct
17 Incorrect 94 ms 604 KB Output isn't correct
18 Incorrect 100 ms 604 KB Output isn't correct
19 Incorrect 542 ms 1116 KB Output isn't correct
20 Incorrect 551 ms 1128 KB Output isn't correct