oj.uz

Submission #918586

# Submission time Handle Problem Language Result Execution time Memory
918586 2024-01-30T07:10:16 Z noyancanturk timeismoney (balkan11_timeismoney) C++17
45 / 100
 2000 ms 620 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],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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 600 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 16 ms 348 KB Output is correct
4 Correct 128 ms 348 KB Output is correct
5 Execution timed out 2066 ms 348 KB Time limit exceeded
6 Execution timed out 2003 ms 348 KB Time limit exceeded
7 Execution timed out 2051 ms 348 KB Time limit exceeded
8 Execution timed out 2033 ms 600 KB Time limit exceeded
9 Correct 6 ms 344 KB Output is correct
10 Correct 33 ms 348 KB Output is correct
11 Correct 14 ms 348 KB Output is correct
12 Correct 123 ms 348 KB Output is correct
13 Correct 137 ms 348 KB Output is correct
14 Execution timed out 2070 ms 348 KB Time limit exceeded
15 Execution timed out 2054 ms 348 KB Time limit exceeded
16 Execution timed out 2063 ms 348 KB Time limit exceeded
17 Execution timed out 2035 ms 344 KB Time limit exceeded
18 Execution timed out 2041 ms 344 KB Time limit exceeded
19 Execution timed out 2051 ms 604 KB Time limit exceeded
20 Execution timed out 2020 ms 620 KB Time limit exceeded