Submission #786434

#TimeUsernameProblemLanguageResultExecution timeMemory
786434minhcooltimeismoney (balkan11_timeismoney)C++17
100 / 100
734 ms796 KiB
#define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e6 + 5; const int oo = 1e9 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n, m; vector<iiii> edges; vector<iiii> edges2; int rt[N], sz[N]; int root(int x){ return (x == rt[x] ? x : rt[x] = root(rt[x])); } bool merge(int x, int y){ x = root(x), y = root(y); if(x == y) return 0; sz[x] += sz[y]; rt[y] = x; return 1; } bool cmp(iiii a, iiii b){ return a.se.fi < b.se.fi; } pair<int, ii> answer = {oo, {0, 0}}; map<ii, ii> mpp; void solve(ii a, ii b){ if(a.fi == b.fi || a.se == b.se) return; //cout << a.fi << " " << a.se << " " << b.fi << " " << b.se << "\n"; //exit(0); if(b.fi < a.fi) swap(a, b); if(a.se < b.se) return; int temp1 = b.fi - a.fi, temp2 = a.se - b.se, cnt = 0; //assert(temp1 >= 0 && temp2 >= 0); //cout << temp1 << " " << temp2 << "\n"; for(auto it : edges){ edges2[cnt] = {{it.fi.fi, it.fi.se}, {it.se.fi * temp2 + it.se.se * temp1, cnt}}; cnt++; } sort(edges2.begin(), edges2.end(), cmp); int tol_a = 0, tol_b = 0; for(int i = 1; i <= n; i++){ sz[i] = 1, rt[i] = i; } for(auto it : edges2){ if(merge(it.fi.fi, it.fi.se)){ //cout << it.fi.fi << " " << it.fi.se << "\n"; tol_a += edges[it.se.se].se.fi; tol_b += edges[it.se.se].se.se; } } answer = min(answer, {tol_a * tol_b, {tol_a, tol_b}}); if(mpp.find({tol_a, tol_b}) == mpp.end()) mpp[{tol_a, tol_b}] = {temp2, temp1}; //cout << tol_a << " " << tol_b << " " << temp2 << " " << temp1 << "\n"; if ((a.se - b.se) * (tol_a - a.fi) == (a.se - tol_b) * (b.fi - a.fi)) { // answer = min(answer, {a.fi * a.se, a}); // answer = min(answer, {b.fi * b.se, b}); return; } solve(a, {tol_a, tol_b}); solve({tol_a, tol_b}, b); } bool cmp1(iiii a, iiii b){ return a.se.fi < b.se.fi; } bool cmp2(iiii a, iiii b){ return a.se.se < b.se.se; } #ifdef local void process(){ cin >> n >> m; for(int i = 1; i <= m; i++){ int x, y, a, b; cin >> x >> y >> a >> b; x++, y++; edges.pb({{x, y}, {a, b}}); } //exit(0); sort(edges.begin(), edges.end(), cmp1); //exit(0); for(int i = 1; i <= n; i++) sz[i] = 1, rt[i] = i; ii tol_1 = {0, 0}; for(auto it : edges) if(merge(it.fi.fi, it.fi.se)) tol_1 = {tol_1.fi + it.se.fi, tol_1.se + it.se.se}; sort(edges.begin(), edges.end(), cmp2); for(int i = 1; i <= n; i++) sz[i] = 1, rt[i] = i; ii tol_2 = {0, 0}; for(auto it : edges) if(merge(it.fi.fi, it.fi.se)) tol_2 = {tol_2.fi + it.se.fi, tol_2.se + it.se.se}; edges2.resize(edges.size()); //exit(0); mpp[tol_1] = {1, 0}; mpp[tol_2] = {0, 1}; answer = min(answer, {tol_1.fi * tol_1.se, tol_1}); answer = min(answer, {tol_2.fi * tol_2.se, tol_2}); solve(tol_1, tol_2); cout << answer.se.fi << " " << answer.se.se << "\n"; //cout << mpp[answer.se].fi << " " << mpp[answer.se].se << "\n"; // edges2.clear(); int cnt = 0; for(auto it : edges){ edges2[cnt] = {{it.fi.fi, it.fi.se}, {it.se.fi * mpp[answer.se].fi + it.se.se * mpp[answer.se].se, cnt}}; cnt++; } sort(edges2.begin(), edges2.end(), cmp); int tol_a = 0, tol_b = 0; for(int i = 1; i <= n; i++){ sz[i] = 1, rt[i] = i; } for(auto it : edges2){ if(merge(it.fi.fi, it.fi.se)){ cout << it.fi.fi - 1 << " " << it.fi.se - 1 << "\n"; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("kek.inp", "r", stdin); // freopen("kek.out", "w", stdout); process(); } #endif

Compilation message (stderr)

timeismoney.cpp: In function 'void process()':
timeismoney.cpp:139:6: warning: unused variable 'tol_a' [-Wunused-variable]
  139 |  int tol_a = 0, tol_b = 0;
      |      ^~~~~
timeismoney.cpp:139:17: warning: unused variable 'tol_b' [-Wunused-variable]
  139 |  int tol_a = 0, tol_b = 0;
      |                 ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...