oj.uz

Submission #1029183

# Submission time Handle Problem Language Result Execution time Memory
1029183 2024-07-20T13:34:52 Z lucri timeismoney (balkan11_timeismoney) C++17
40 / 100
 2000 ms 1112 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)
        for(long long j=0;j<=260;++j)
        {
            calculeaza(i,j);
            if(sumt*summ<vmax)
            {
                st=sumt,sm=summ;
                vmax=sumt*summ;
                p1=i;
                p2=j;
            }
        }
    cout<<st<<' '<<sm<<'\n';
    scrie(1,1);
    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 344 KB Output is correct
2 Correct 52 ms 348 KB Output is correct
3 Correct 67 ms 348 KB Output is correct
4 Correct 210 ms 444 KB Output is correct
5 Correct 1502 ms 468 KB Output is correct
6 Correct 1020 ms 464 KB Output is correct
7 Execution timed out 2045 ms 604 KB Time limit exceeded
8 Execution timed out 2037 ms 1112 KB Time limit exceeded
9 Correct 48 ms 444 KB Output is correct
10 Incorrect 113 ms 348 KB Output isn't correct
11 Incorrect 71 ms 344 KB Output isn't correct
12 Incorrect 225 ms 348 KB Output isn't correct
13 Correct 267 ms 344 KB Output is correct
14 Incorrect 1936 ms 348 KB Output isn't correct
15 Incorrect 1478 ms 464 KB Output isn't correct
16 Execution timed out 2059 ms 604 KB Time limit exceeded
17 Execution timed out 2040 ms 600 KB Time limit exceeded
18 Execution timed out 2013 ms 344 KB Time limit exceeded
19 Execution timed out 2009 ms 1112 KB Time limit exceeded
20 Execution timed out 2024 ms 1112 KB Time limit exceeded