oj.uz

Submission #886245

# Submission time Handle Problem Language Result Execution time Memory
886245 2023-12-11T15:50:20 Z Rafi22 timeismoney (balkan11_timeismoney) C++14
45 / 100
 127 ms 1496 KB 
#include <bits/stdc++.h>

//#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
int mod=1000000007;
int mod1=998244353;

const int N=207,M=10007;

int U[N],V[N],X[N],Y[N];

bool cmp(pair<int,int>L,pair<int,int>R)
{
    return L.st*R.nd<R.st*L.nd;
}
vector<int>W;
int n;

int r[N];
int Find(int v)
{
    if(r[v]==v) return v;
    return r[v]=Find(r[v]);
}

vector<pair<int,int>>ans,act;
int sX,sY,bX,bY,res=2*inf;

void Union(int u,int v,int i)
{
    int uu=Find(u),vv=Find(v);
    if(uu==vv) return ;
    r[uu]=vv;
    act.pb({u,v});
    sX+=X[i];
    sY+=Y[i];
}

void calc()
{
    for(int i=0;i<n;i++) r[i]=i;
    act.clear();
    sX=0;
    sY=0;
    for(auto i:W)
    {
        Union(U[i],V[i],i);
        if(sX*sY>=res) break;
    }
    if(sX*sY<res)
    {
        res=sX*sY;
        ans=act;
        bX=sX;
        bY=sY;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin>>n>>m;
    vector<pair<int,int>>ord;
    for(int i=0;i<m;i++)
    {
        cin>>U[i]>>V[i]>>X[i]>>Y[i];
        ord.pb({X[i],i});
    }
    sort(all(ord));
    for(auto [c,x]:ord) W.pb(x);
    vector<pair<int,int>>F;
    F.pb({0,1});
    for(int a=1;a<=255;a++) for(int b=1;b<=255;b++) if(__gcd(a,b)==1) F.pb({a,b});
    sort(all(F),cmp);
    calc();
    for(auto [a,b]:F)
    {
        for(int i=0;i<m;i++)
        {
            int j=i;
            while(j>0&&a*X[W[j]]+b*Y[W[j]]<a*X[W[j-1]]+b*Y[W[j-1]])
            {
                swap(W[j],W[j-1]);
                j--;
            }
        }
        calc();
    }
    cout<<bX<<" "<<bY<<endl;
    for(auto [x,y]:ans) cout<<x<<" "<<y<<endl;


    return 0;
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [c,x]:ord) W.pb(x);
      |              ^
timeismoney.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for(auto [a,b]:F)
      |              ^
timeismoney.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |     for(auto [x,y]:ans) cout<<x<<" "<<y<<endl;
      |              ^

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 988 KB Output is correct
2 Correct 12 ms 992 KB Output is correct
3 Correct 18 ms 992 KB Output is correct
4 Correct 40 ms 1144 KB Output is correct
5 Runtime error 6 ms 1496 KB Execution killed with signal 11
6 Runtime error 6 ms 1496 KB Execution killed with signal 11
7 Runtime error 1 ms 604 KB Execution killed with signal 11
8 Runtime error 1 ms 472 KB Execution killed with signal 11
9 Correct 11 ms 1056 KB Output is correct
10 Correct 14 ms 992 KB Output is correct
11 Correct 17 ms 992 KB Output is correct
12 Correct 39 ms 992 KB Output is correct
13 Correct 41 ms 988 KB Output is correct
14 Runtime error 6 ms 1496 KB Execution killed with signal 11
15 Runtime error 6 ms 1496 KB Execution killed with signal 11
16 Runtime error 1 ms 604 KB Execution killed with signal 11
17 Runtime error 1 ms 604 KB Execution killed with signal 11
18 Runtime error 1 ms 600 KB Execution killed with signal 11
19 Runtime error 1 ms 604 KB Execution killed with signal 11
20 Runtime error 1 ms 604 KB Execution killed with signal 11