oj.uz

Submission #480772

# Submission time Handle Problem Language Result Execution time Memory
480772 2021-10-18T03:27:35 Z phamhoanghiep timeismoney (balkan11_timeismoney) C++14
95 / 100
 410 ms 664 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
vector<iiii> edges;
vector<ii> rate;
const int bl=30;
const int maxn=202;
int n,m;
int a,b;
// MST: kruskal ??
int pset[maxn];
int sz[maxn];
int cnt_set;
void init() {
    for(int i=1 ; i<=n ; i++) {
        pset[i]=i;
        sz[i]=1;
    }
    cnt_set=n;
}
int find_set(int s) {
    if(s==pset[s]) return s;
    return pset[s]=find_set(pset[s]);
}
void union_set(int u, int v) {
    if(sz[u]>sz[v]) swap(u,v);
    pset[u]=v;
    sz[v]+=sz[u];
}
pair<int,int> solve() {
    init();
    int sum_t=0;
    int sum_c=0;
    for(iiii tmp: edges) {
        int u=tmp.fi.fi;
        int v=tmp.fi.se;
        int t=tmp.se.fi;
        int c=tmp.se.se;
        int fu=find_set(u);
        int fv=find_set(v);
        if(fu==fv) continue;
        else {
            union_set(fu,fv);
            sum_t+=t;
            sum_c+=c;
        }
    }
    return ii(sum_t,sum_c);
}
signed main() {
    for(int i=0 ; i<=bl ; i++) {
        for(int j=0 ; j<=bl ; j++) {
            if(i==0&&j==0) continue;
            if(__gcd(i,j)==1) {
                rate.push_back(ii(i,j));
            }
        }
    }
    cin>>n>>m;
    for(int i=1 ; i<=m ; i++) {
        int u,v,t,c;
        cin>>u>>v>>t>>c;
        u++; v++;
        edges.push_back(iiii(ii(u,v),ii(t,c)));
    }
    int finale=INT_MAX;
    int anst,ansc;
    ii X=ii(0,0);
    for(ii tmp: rate) {
        a=tmp.fi;
        b=tmp.se;
        sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
        ii res=solve();
        if(res.fi*res.se<finale) {
            finale=res.fi*res.se;
            anst=res.fi;
            ansc=res.se;
            X=ii(a,b);
        }
    }
    a=X.fi;
    b=X.se;
    cout<<anst<<' '<<ansc<<'\n';
    sort(edges.begin(),edges.end(),[](const iiii &x, const iiii &y){return x.se.fi*a+x.se.se*b<y.se.fi*a+y.se.se*b;});
    init();
    for(iiii tmp: edges) {
        int u=tmp.fi.fi;
        int v=tmp.fi.se;
        int t=tmp.se.fi;
        int c=tmp.se.se;
        int fu=find_set(u);
        int fv=find_set(v);
        if(fu==fv) continue;
        else {
            union_set(fu,fv);
            cout<<u-1<<' '<<v-1<<'\n';
        }
    }
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:92:13: warning: unused variable 't' [-Wunused-variable]
   92 |         int t=tmp.se.fi;
      |             ^
timeismoney.cpp:93:13: warning: unused variable 'c' [-Wunused-variable]
   93 |         int c=tmp.se.se;
      |             ^
timeismoney.cpp:86:28: warning: 'ansc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     cout<<anst<<' '<<ansc<<'\n';
      |                            ^~~~
timeismoney.cpp:86:17: warning: 'anst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     cout<<anst<<' '<<ansc<<'\n';
      |                 ^~~

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 6 ms 316 KB Output is correct
6 Correct 6 ms 204 KB Output is correct
7 Correct 31 ms 368 KB Output is correct
8 Correct 163 ms 664 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 11 ms 316 KB Output is correct
15 Correct 10 ms 312 KB Output is correct
16 Correct 66 ms 332 KB Output is correct
17 Correct 66 ms 332 KB Output is correct
18 Correct 66 ms 348 KB Output is correct
19 Correct 410 ms 588 KB Output is correct
20 Incorrect 397 ms 588 KB Output isn't correct