Submission #918586

#	Time	Username	Problem	Language	Result	Execution time	Memory
918586		noyancanturk	timeismoney (balkan11_timeismoney)	C++17	45 / 100	2070 ms	620 KiB

timeismoney

#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{
    signed 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],sz[201];
inline void init(int n){
    for(int i=0;i<n;i++){
        parent[i]=i;
        sz[i]=1;
    }
}
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){
        if(sz[x]<sz[y])swap(x,y);
        parent[y]=x;
        sz[x]+=sz[y];
        return 1;
    }
    return 0;
}
    
#define lll 51001
    
bitset<lll>dp=1;
inline void solve(){
    int n,m;
    cin>>n>>m;
    edge v[m];
    int cnt[256];
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<m;i++){
        cin>>v[i].x>>v[i].y>>v[i].c1>>v[i].c2;
        cnt[v[i].c1]++;
    }
    edge ans[n-1],cur[n-1];
    int ansbest=1e13;
    for(int i=1;i<256;i++){
        for(int j=1;j<cnt[i];j<<=1){
            dp|=dp<<(i*j);
            cnt[i]-=j;
        }
        dp|=dp<<(i*cnt[i]);
    }
    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";
            #define cost(x) (x.c1*mid+x.c2*AA)
            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 / 100