oj.uz

답안 #480773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480773 2021-10-18T03:28:04 Z phamhoanghiep 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
 1072 ms 680 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=50;
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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 4 ms 320 KB Output is correct
5 Correct 17 ms 204 KB Output is correct
6 Correct 13 ms 324 KB Output is correct
7 Correct 81 ms 356 KB Output is correct
8 Correct 425 ms 588 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 5 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 32 ms 204 KB Output is correct
15 Correct 24 ms 328 KB Output is correct
16 Correct 168 ms 360 KB Output is correct
17 Correct 166 ms 332 KB Output is correct
18 Correct 173 ms 352 KB Output is correct
19 Correct 1039 ms 680 KB Output is correct
20 Correct 1072 ms 588 KB Output is correct