oj.uz

Submission #1029178

# Submission time Handle Problem Language Result Execution time Memory
1029178 2024-07-20T13:33:10 Z lucri timeismoney (balkan11_timeismoney) C++17
50 / 100
 591 ms 1216 KB 
#include <bits/stdc++.h>
using namespace std;
long long t[210],u[10010],v[10010],ti[10010],mo[10010],n,m,vmax=2000000000000000000,st,sm,p1,p2;
long long sumt,summ;
struct muchii{long long u,v,val,valt,valm;}a[10010];
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.valt;
}
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[t[a[i].u]]=t[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[t[a[i].u]]=t[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(1,1);
    return 0;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 12 ms 348 KB Output is correct
6 Correct 7 ms 480 KB Output is correct
7 Correct 64 ms 572 KB Output is correct
8 Correct 591 ms 1116 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 1 ms 344 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 Correct 2 ms 344 KB Output is correct
14 Incorrect 15 ms 488 KB Output isn't correct
15 Incorrect 12 ms 348 KB Output isn't correct
16 Incorrect 91 ms 572 KB Output isn't correct
17 Incorrect 109 ms 348 KB Output isn't correct
18 Incorrect 97 ms 576 KB Output isn't correct
19 Incorrect 550 ms 1216 KB Output isn't correct
20 Incorrect 563 ms 1116 KB Output isn't correct