oj.uz

Submission #918583

# Submission time Handle Problem Language Result Execution time Memory
918583 2024-01-30T07:08:12 Z noyancanturk timeismoney (balkan11_timeismoney) C++17
45 / 100
 2000 ms 856 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{
    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];
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 1112 ms 592 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 14 ms 472 KB Output is correct
4 Correct 134 ms 452 KB Output is correct
5 Execution timed out 2017 ms 344 KB Time limit exceeded
6 Execution timed out 2036 ms 348 KB Time limit exceeded
7 Execution timed out 2036 ms 344 KB Time limit exceeded
8 Execution timed out 2067 ms 604 KB Time limit exceeded
9 Correct 7 ms 348 KB Output is correct
10 Correct 33 ms 344 KB Output is correct
11 Correct 14 ms 348 KB Output is correct
12 Correct 125 ms 448 KB Output is correct
13 Correct 132 ms 344 KB Output is correct
14 Execution timed out 2065 ms 348 KB Time limit exceeded
15 Execution timed out 2040 ms 456 KB Time limit exceeded
16 Execution timed out 2044 ms 348 KB Time limit exceeded
17 Execution timed out 2049 ms 348 KB Time limit exceeded
18 Execution timed out 2027 ms 600 KB Time limit exceeded
19 Execution timed out 2037 ms 856 KB Time limit exceeded
20 Execution timed out 2013 ms 600 KB Time limit exceeded