Submission #245799

#TimeUsernameProblemLanguageResultExecution timeMemory
245799quocnguyen1012Job Scheduling (IOI19_job)C++14
100 / 100
827 ms20856 KiB
#ifndef LOCAL #include "job.h" #endif // LOCAL #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back #define ar array using namespace std; typedef long long ll; typedef pair<int, int> ii; const int maxn = 2e5 + 5; int cost[maxn], tim[maxn]; int N; int lab[maxn], mark[maxn]; ll t = 0, res; int finds(int u) { if(lab[u] == u) return u; return lab[u] = finds(lab[u]); } struct cmp { bool operator ()(int a, int b) const { if(1ll * cost[a] * tim[b] != 1ll * cost[b] * tim[a]) return 1ll * cost[a] * tim[b] > 1ll * cost[b] * tim[a]; return a < b; } }; set<int, cmp> se; ll scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) { N = p.size(); for(int i = 0; i < N; ++i){ tim[i] = d[i]; cost[i] = u[i]; lab[i] = i; } for(int i = 0; i < N; ++i) se.insert(i); for(int i = 0; i < N; ++i){ int now = *se.begin(); se.erase(now); //cerr << now << '\n'; if(p[now] == -1 || mark[finds(p[now])]){ t += tim[now]; res += 1ll * cost[now] * t; mark[now] = 1; continue; } int top = finds(p[now]); se.erase(top); res -= 1ll * cost[top] * tim[now]; cost[top] += cost[now]; tim[top] += tim[now]; se.insert(top); lab[now] = top; } return res; } #ifdef LOCAL signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("A.INP", "r", stdin); freopen("A.OUT", "w", stdout); #endif // LOCAL int n; cin >> n; vector<int> p(n), u(n), d(n); for(auto & it : p) cin >> it; for(auto & it : u) cin >> it; for(auto & it : d) cin >> it; cout << scheduling_cost(p, u, d); } #endif // LOCAL
#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...