Submission #1142286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142286		mohyay	timeismoney (balkan11_timeismoney)	C++20	0 / 100	7 ms	964 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
const ll mod = 1e9 + 7;
struct node {
    ll i, j, x, y;
};
vector<node> inp;
ll dsu[112345], n, m;
ll findboss(ll a) {
    if (dsu[a] == a) return a;
    return findboss(dsu[a]);
}
void merge(ll a, ll b) {
    a = findboss(a);
    b = findboss(b);
    dsu[a] = dsu[b];
}
vector<pair<ll,ll>> mst(ll a, ll b) {
    //cout << a << " mst " << b << endl;
    for (int i=0; i<=200; i++) dsu[i] = i;
    vector<pair<pair<ll, ll>, pair<ll, ll>>> v(m);
    for (int i=0; i<m; i++) {
        v[i] = {{inp[i].x * a, inp[i].y * b}, {inp[i].i, inp[i].j}};
    }
    sort(v.begin(), v.end());
    vector<pair<ll,ll>> ans;
    ll time=0, cost=0;
    for (int k=0; k<m; k++) {
        ll i = v[k].pS.pF, j = v[k].pS.pS;
        if (findboss(i) == findboss(j)) continue;
        merge(i, j);
        ans.pb({i, j});
        time += v[k].pF.pF;
        cost += v[k].pF.pS;
    }

    vector<pair<ll, ll>> ret; ret.push_back({time, cost});
    for (auto p : ans) ret.push_back(p);
    return ret;
}
vector<pair<ll,ll>>& cmp(vector<pair<ll,ll>> &v, vector<pair<ll,ll>> &v1) {
    if (v[0].pF * v[0].pS <= v1[0].pF * v1[0].pS)
        return v;
    else
        return v1;
}
vector<pair<ll,ll>>& quickhull(ll t1, ll c1, ll t2, ll c2) {
    //cout << t1 SP c1 SP t2 SP c2 << endl;
    vector<pair<ll,ll>> ans = mst(c2 - c1, t1 - t2);
    if ((ans[0].pF == t1 && ans[0].pS == c1) || ans[0].pF == t2 && ans[0].pS == c2) return ans;
    return cmp(quickhull(ans[0].pF, ans[0].pS, t1, c1), quickhull(ans[0].pF, ans[0].pS, t2, c2));
}
int main() {
    //ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        ll a, b, x, y;
        cin >> a >> b >> x >> y;
        inp.pb({a, b, x, y});
    }
    //vector<pair<ll, ll>> time = mst(1, 0);
    //vector<pair<ll, ll>> cost = mst(0, 1);
    //ll t1 = time[0].pF, c1 = time[0].pS, t2 = cost[0].pF, c2 = cost[0].pS;

    // vector<pair<ll,ll>> ans = quickhull(t1, c1, t2, c2);
    vector<pair<ll,ll>> ans =  mst(1,0);
    for (auto [i, j] : ans) cout << i SP j << endl;
}

Compilation message (stderr)

timeismoney.cpp: In function 'std::vector<std::pair<long long int, long long int> >& quickhull(ll, ll, ll, ll)':
timeismoney.cpp:56:92: warning: reference to local variable 'ans' returned [-Wreturn-local-addr]
   56 |     if ((ans[0].pF == t1 && ans[0].pS == c1) || ans[0].pF == t2 && ans[0].pS == c2) return ans;
      |                                                                                            ^~~
timeismoney.cpp:55:25: note: declared here
   55 |     vector<pair<ll,ll>> ans = mst(c2 - c1, t1 - t2);
      |                         ^~~

• Subtask 1: 0 / 100