Submission #42433

#TimeUsernameProblemLanguageResultExecution timeMemory
42433choikiwontimeismoney (balkan11_timeismoney)C++14
55 / 100
14 ms1480 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; int cross(pii a, pii b) { return a.first * b.second - a.second * b.first; } int ccw(pii a, pii b, pii c) { pii p = pii(b.first - a.first, b.second - a.second); pii q = pii(c.first - a.first, c.second - a.second); return cross(p, q); } int N, M, T, C; struct Edge { int u, v, t, c; }; Edge edge[10010]; vector<pii> sol, tmp; bool cmp(Edge a, Edge b) { return T * a.t + C * a.c < T * b.t + C * b.c; } struct DSU { int par[202], rnk[202]; void init() { for(int i = 0; i < N; i++) { par[i] = i; rnk[i] = 0; } } int f(int u) { if(par[u] == u) return u; else return par[u] = f(par[u]); } void mrg(int u, int v) { u = f(u); v = f(v); if(u == v) return; if(rnk[u] < rnk[v]) swap(u, v); par[v] = u; if(rnk[u] == rnk[v]) rnk[u]++; } } dsu; pii solve(int a, int b) { T = a; C = b; sort(edge, edge + M, cmp); pii ret = pii(0, 0); dsu.init(); tmp.clear(); for(int i = 0; i < M; i++) { int u = edge[i].u; int v = edge[i].v; int t = edge[i].t; int c = edge[i].c; if(dsu.f(u) == dsu.f(v)) continue; dsu.mrg(u, v); ret.first += t; ret.second += c; tmp.push_back(pii(u, v)); } return ret; } pii ans = pii(1e9, 1); void rec(pii s, pii e) { int a = e.first - s.first; int b = s.second - e.second; pii m = solve(a, b); if(ccw(s, m, e) > 0) { if(ans.first * ans.second > m.first * m.second) { ans = m; sol = tmp; } rec(s, m); rec(m, e); } } int main() { scanf("%d %d", &N, &M); for(int i = 0; i < M; i++) { int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c); edge[i] = {u, v, t, c}; } pii s = solve(1, 0); if(ans.first * ans.second > s.first * s.second) { ans = s; sol = tmp; } pii e = solve(0, 1); if(ans.first * ans.second > e.first * e.second) { ans = e; sol = tmp; } rec(s, e); printf("%d %d\n", ans.first, ans.second); for(int i = 0; i < sol.size(); i++) { printf("%d %d\n", sol[i].first, sol[i].second); } }

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < sol.size(); i++) {
                      ^
timeismoney.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
timeismoney.cpp:93:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c);
                                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...