Submission #43273

#TimeUsernameProblemLanguageResultExecution timeMemory
43273ToMoClonetimeismoney (balkan11_timeismoney)C++14
0 / 100
2055 ms65536 KiB
/*input 5 7 0 1 161 79 0 2 161 15 0 3 13 153 1 4 142 183 2 4 236 80 3 4 40 241 2 1 65 92 */ #include <bits/stdc++.h> using namespace std; #define Point pair<int, int> struct Edge { int u, v, val1, val2; Edge(int _u, int _v, int _val1, int _val2) : u(_u), v(_v), val1(_val1), val2(_val2) {} }; int Arr[205], n, m, res = 2e9; Point base; vector<Edge> edges; vector<pair<int, int> > trace; int root(int x) { if(x == Arr[x]) return x; return Arr[x] = root(Arr[x]); } Point Kruskal(int x1, int y1) { sort(edges.begin(), edges.end(), [&](const Edge &x, const Edge &y) { int X = x.val1 * x1 + x.val2 * y1; int Y = y.val1 * x1 + y.val2 * y1; return (X != Y) ? (X < Y) : (x.val1 * x1 < y.val1 * x1); }); for(int i = 1; i <= n; ++i) Arr[i] = i; int Ans = 0, valx = 0, valy = 0; vector<pair<int, int> > Dat; for(auto cur : edges) { if(root(cur.u) == root(cur.v)) continue; if((int)Dat.size() == n - 1) break; Arr[root(cur.u)] = root(cur.v); Ans += cur.val1 * x1 + cur.val2 * y1; valx += cur.val1, valy += cur.val2; Dat.push_back(make_pair(cur.u, cur.v)); } if(valx * valy < res) { res = valx * valy, base = make_pair(valx, valy); trace = move(Dat); } return make_pair(valx, valy); } void solve(Point a, Point b) { Point X = Kruskal(a.second - b.second, b.first - a.first); if(X != a && X != b) solve(a, X), solve(X, b); } int main(){ scanf("%d%d", &n, &m); edges.reserve(m); for(int i = 0; i < m; ++i) { int x, y, t, c; scanf("%d%d%d%d", &x, &y, &t, &c); edges.push_back(Edge(x + 1, y + 1, t, c)); } Point maxt = Kruskal(1, 0), maxc = Kruskal(0, 1); solve(maxt, maxc); printf("%d %d\n", base.first, base.second); for(auto v : trace) printf("%d %d\n", v.first, v.second); }

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:68:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
timeismoney.cpp:72:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, t, c; scanf("%d%d%d%d", &x, &y, &t, &c);
                                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...