oj.uz

Submission #918566

# Submission time Handle Problem Language Result Execution time Memory
918566 2024-01-30T06:49:42 Z noyancanturk timeismoney (balkan11_timeismoney) C++17
45 / 100
 2000 ms 860 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1e5+100;
#else
    const int lim=3e3+100;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int int64_t
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

struct edge{
    int x,y,c1,c2;
    inline edge(){}
    inline edge(int x,int y,int c1,int c2)
    :x(x),y(y),c1(c1),c2(c2){}
};

int parent[201];
inline void init(int n){
    for(int i=0;i<n;i++)parent[i]=i;
}
inline int find(int i){
    if(parent[i]==i)return i;
    return parent[i]=find(parent[i]);
}
inline bool unite(int i,int j){
    int x=find(i),y=find(j);
    if(x^y){
        parent[x]=y;
        return 1;
    }
    return 0;
}

#define lll 51001

bitset<lll>dp=1;
inline void solve(){
    int n,m;
    cin>>n>>m;
    edge v[m];
    for(int i=0;i<m;i++){
        cin>>v[i].x>>v[i].y>>v[i].c1>>v[i].c2;
    }
    edge ans[n-1],cur[n-1];
    int ansbest=1e13;
    for(int i=0;i<m;i++){
        dp|=dp<<v[i].c1;
    }
    for(int AA=n-1;AA<lll;AA++){
        if(!dp[AA])continue;
        int l=n-1,r=lll-1;
        //cerr<<AA<<" AA\n";
        while(l<=r){
            int mid=(l+r)>>1;
            //if(AA==279)cerr<<l<<" "<<mid<<" "<<r<<"\n";
            sort(v,v+m,[&](edge&x,edge&y) -> bool {
                return x.c1*mid+x.c2*AA<y.c1*mid+y.c2*AA;
            });
            init(n);
            int curi=0,A=0,B=0;
            for(int i=0;i<m&&curi<n-1;i++){
                if(unite(v[i].x,v[i].y)){
                    cur[curi++]=v[i];
                    A+=v[i].c1;
                    B+=v[i].c2;
                    if(AA<A){
                        l=mid+1;
                        goto fail;
                    }
                }
            }
            /*
            if(AA==279){
                cerr<<A<<" "<<B<<" "<<A*B<<" "<<ansbest<<" result\n";
                }
            */
            if(A*B<ansbest){
                for(int i=0;i<n-1;i++){
                    ans[i]=cur[i];
                }
                ansbest=A*B;
            }
            r=mid-1;
            fail:;
        }
    }
    int A=0,B=0;
    for(int i=0;i<n-1;i++){
        A+=ans[i].c1;
        B+=ans[i].c2;
    }
    cout<<A<<" "<<B<<"\n";
    for(int i=0;i<n-1;i++){
        cout<<ans[i].x<<" "<<ans[i].y<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else

#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 472 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 14 ms 344 KB Output is correct
4 Correct 126 ms 452 KB Output is correct
5 Execution timed out 2028 ms 344 KB Time limit exceeded
6 Execution timed out 2048 ms 348 KB Time limit exceeded
7 Execution timed out 2103 ms 344 KB Time limit exceeded
8 Execution timed out 2050 ms 860 KB Time limit exceeded
9 Correct 6 ms 348 KB Output is correct
10 Correct 33 ms 348 KB Output is correct
11 Correct 14 ms 472 KB Output is correct
12 Correct 125 ms 348 KB Output is correct
13 Correct 133 ms 344 KB Output is correct
14 Execution timed out 2008 ms 596 KB Time limit exceeded
15 Execution timed out 2036 ms 348 KB Time limit exceeded
16 Execution timed out 2039 ms 348 KB Time limit exceeded
17 Execution timed out 2064 ms 348 KB Time limit exceeded
18 Execution timed out 2048 ms 348 KB Time limit exceeded
19 Execution timed out 2057 ms 860 KB Time limit exceeded
20 Execution timed out 2051 ms 860 KB Time limit exceeded