Submission #146759

#TimeUsernameProblemLanguageResultExecution timeMemory
146759qkxwsmJob Scheduling (IOI19_job)C++14
100 / 100
691 ms37496 KiB
#include "job.h" #include <bits/stdc++.h> using namespace std; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) #define SZ(x) ((int) ((x).size())) #define ALL(x) (x).begin(), (x).end() #define MAXN 200013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; typedef pair<ld, int> pdi; typedef pair<pll, int> ppi; int N; int parent[MAXN], link[MAXN]; bitset<MAXN> taken; vi edge[MAXN]; pll arr[MAXN]; int dsu[MAXN]; struct cmp { bool operator() (const ppi &a, const ppi &b) const { if (a.fi.fi * b.fi.se != a.fi.se * b.fi.fi) return a.fi.fi * b.fi.se < a.fi.se * b.fi.fi; return a.se < b.se; } }; set<ppi, cmp> s; ll ans = 0, t = 0; int get(int u) { return (u == dsu[u] ? u : dsu[u] = get(dsu[u])); } void merge(int u, int v) { u = get(u); v = get(v); if (u == v) return; if (u < v) swap(u, v); dsu[u] = v; return; } ll scheduling_cost(vi p, vi u, vi d) { N = SZ(p); // cerr << "HI\n"; FOR(i, 0, N) { parent[i] = p[i]; if (i == 0) parent[i] = N; else edge[parent[i]].PB(i); arr[i] = {u[i], d[i]}; s.insert({{arr[i].fi, arr[i].se}, i}); link[i] = parent[i]; ans += arr[i].fi * arr[i].se; dsu[i] = i; // cerr << "parent " << parent[i] << endl; } dsu[N] = N; taken[N] = true; FOR(i, 0, N) { int u = (prev(s.end())) -> se; // cerr << "ERASE " << u << endl; s.erase(prev(s.end())); int v = get(parent[get(u)]); if (taken[v]) { ans += arr[u].fi * t; t += arr[u].se; taken[u] = true; continue; //cool gg } // cerr << "BAD " << u << ' ' << v << endl; // cerr << "ONE\n"; merge(u, v); // cerr << "SEARCH " << arr[v].fi << ' ' << arr[v].se << ' ' << v << endl; s.erase(s.find({{arr[v].fi, arr[v].se}, v})); // cerr << "TWO\n"; ans += arr[v].se * arr[u].fi; arr[v].fi += arr[u].fi; arr[v].se += arr[u].se; s.insert({{arr[v].fi, arr[v].se}, v}); // cerr << "INSERT " << arr[v].fi << ' ' << arr[v].se << ' ' << v << endl; } return ans; //yo uwant to take stuff with high fi/se first }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...