oj.uz

Submission #1029231

# Submission time Handle Problem Language Result Execution time Memory
1029231 2024-07-20T14:06:29 Z lucri timeismoney (balkan11_timeismoney) C++17
50 / 100
 858 ms 1492 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]);
}
long long x,xx,y,yy;
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';
        }
    }
}
long long det(long long x,long long y,long long xx,long long yy,long long xxx,long long yyy)
{
    return x*yy+xx*yyy+xxx*y-xx*y-xxx*yy-x*yyy;
}
unordered_set<long long>viz;
void imbunatatire(int x,int y,int xx,int yy)
{
    if(viz.find(x*1000000000000000000+y*1000000000000+xx*1000000+yy)!=viz.end())
        return;
    viz.insert(x*1000000000000000000+y*1000000000000+xx*1000000+yy);
    calculeaza(abs(xx-x),abs(yy-y));
    if(sumt*summ<vmax)
    {
        st=sumt,sm=summ;
        vmax=sumt*summ;
        p1=abs(xx-x);
        p2=abs(yy-y);
    }
    if(det(x,y,xx,yy,sumt,summ)==0)
        return;
    int c1=sumt,c2=summ;
    imbunatatire(x,y,sumt,summ);
    imbunatatire(xx,yy,sumt,summ);
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=m;++i)
        cin>>u[i]>>v[i]>>ti[i]>>mo[i];
    calculeaza(1,0);
    if(sumt*summ<vmax)
    {
        st=sumt,sm=summ;
        vmax=sumt*summ;
        p1=1;
        p2=0;
    }
    x=sumt;
    y=summ;
    calculeaza(0,1);
    if(sumt*summ<vmax)
    {
        st=sumt,sm=summ;
        vmax=sumt*summ;
        p1=0;
        p2=1;
    }
    xx=sumt;
    yy=summ;
    imbunatatire(x,y,xx,yy);
    cout<<st<<' '<<sm<<'\n';
    scrie(1,1);
    return 0;
}

Compilation message

timeismoney.cpp: In function 'void imbunatatire(int, int, int, int)':
timeismoney.cpp:73:9: warning: unused variable 'c1' [-Wunused-variable]
   73 |     int c1=sumt,c2=summ;
      |         ^~
timeismoney.cpp:73:17: warning: unused variable 'c2' [-Wunused-variable]
   73 |     int c1=sumt,c2=summ;
      |                 ^~

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 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 2 ms 604 KB Output is correct
8 Correct 10 ms 1116 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 4 ms 348 KB Output isn't correct
15 Incorrect 5 ms 448 KB Output isn't correct
16 Incorrect 68 ms 616 KB Output isn't correct
17 Incorrect 98 ms 600 KB Output isn't correct
18 Incorrect 81 ms 596 KB Output isn't correct
19 Incorrect 858 ms 1492 KB Output isn't correct
20 Incorrect 839 ms 1152 KB Output isn't correct