답안 #296909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
296909 2020-09-11T04:46:52 Z balbit 시간이 돈 (balkan11_timeismoney) C++14
15 / 100
2000 ms 896 KB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e6+5;

struct Ed{
    int a,b,u,v;
};
int n,m;
int par[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void reset() {
    for (int i = 0; i<n; ++i) par[i] = i;
}

signed main(){
    IOS();
    vector<Ed> es;
    cin>>n>>m;
    for (int i = 0; i<m; ++i) {
        int u,v,a,b; cin>>u>>v>>a>>b;
        es.pb({a,b,u,v});
    }
    int re = 1000000;
    vector<Ed> gg;
    int bstA, bstB;
    for (int a = 1; a <= 255; ++a) {
        for (int b = 1; b <= 255; ++b) {
            sort(ALL(es),[&](Ed e1, Ed e2){return e1.a * a + e1.b * b < e2.a * a + e2.b * b;});
            reset();
            int done = 0;
            int A = 0, B = 0;
            vector<int> tmp ;
            for (int i = 0; i<SZ(es) && done != n-1; ++i) {
                if (find(es[i].v) != find(es[i].u)) {
                    ++done; par[find(es[i].v)] = find(es[i].u);
                    A += es[i].a, B += es[i].b;
                    tmp.pb(i);
                }
            }
            if (A*B < re) {
                re = A*B;
                bstA = A, bstB = B;
                gg.clear();
                for (int x : tmp) gg.pb(es[x]);
            }
        }
    }
    cout<<bstA<< ' ' << bstB<<endl;
    for (Ed & e : gg) {
        cout<<e.u<<' '<<e.v<<endl;
    }
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:22:14: warning: 'bstB' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 | #define endl '\n'
      |              ^~~~
timeismoney.cpp:70:15: note: 'bstB' was declared here
   70 |     int bstA, bstB;
      |               ^~~~
timeismoney.cpp:93:18: warning: 'bstA' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     cout<<bstA<< ' ' << bstB<<endl;
      |                  ^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 531 ms 504 KB Output isn't correct
2 Correct 36 ms 384 KB Output is correct
3 Incorrect 64 ms 384 KB Output isn't correct
4 Incorrect 196 ms 504 KB Output isn't correct
5 Incorrect 1061 ms 384 KB Output isn't correct
6 Incorrect 884 ms 504 KB Output isn't correct
7 Execution timed out 2045 ms 384 KB Time limit exceeded
8 Execution timed out 2028 ms 896 KB Time limit exceeded
9 Correct 38 ms 384 KB Output is correct
10 Correct 62 ms 384 KB Output is correct
11 Incorrect 65 ms 384 KB Output isn't correct
12 Incorrect 218 ms 632 KB Output isn't correct
13 Incorrect 214 ms 504 KB Output isn't correct
14 Incorrect 1201 ms 504 KB Output isn't correct
15 Incorrect 1177 ms 412 KB Output isn't correct
16 Execution timed out 2065 ms 384 KB Time limit exceeded
17 Execution timed out 2056 ms 384 KB Time limit exceeded
18 Execution timed out 2067 ms 384 KB Time limit exceeded
19 Execution timed out 2036 ms 896 KB Time limit exceeded
20 Execution timed out 2017 ms 896 KB Time limit exceeded