oj.uz

Submission #918574

# Submission time Handle Problem Language Result Execution time Memory
918574 2024-01-30T06:58:07 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];
    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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 472 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 131 ms 456 KB Output is correct
5 Execution timed out 2045 ms 344 KB Time limit exceeded
6 Execution timed out 2057 ms 348 KB Time limit exceeded
7 Execution timed out 2044 ms 348 KB Time limit exceeded
8 Execution timed out 2044 ms 856 KB Time limit exceeded
9 Correct 9 ms 604 KB Output is correct
10 Correct 34 ms 344 KB Output is correct
11 Correct 15 ms 476 KB Output is correct
12 Correct 126 ms 456 KB Output is correct
13 Correct 153 ms 472 KB Output is correct
14 Execution timed out 2045 ms 344 KB Time limit exceeded
15 Execution timed out 2071 ms 348 KB Time limit exceeded
16 Execution timed out 2055 ms 348 KB Time limit exceeded
17 Execution timed out 2023 ms 344 KB Time limit exceeded
18 Execution timed out 2037 ms 344 KB Time limit exceeded
19 Execution timed out 2071 ms 860 KB Time limit exceeded
20 Execution timed out 2097 ms 856 KB Time limit exceeded