Submission #211343

#TimeUsernameProblemLanguageResultExecution timeMemory
211343eric_xiaoJob Scheduling (IOI19_job)C++14
100 / 100
668 ms24128 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll N,t = 0,ans = 0; ll DSU[300009],fin[300009]; vector<ll> tim,cost; ll Find(ll a) { if(a == DSU[a]) return a; DSU[a] = Find(DSU[a]); return DSU[a]; } struct cmp{ bool operator()(ll a, ll b)const { if(cost[a]*tim[b] != cost[b]*tim[a]) return cost[a]*tim[b] > cost[b]*tim[a]; return a < b; } }; set<ll,cmp> st; ll scheduling_cost(vector<int> P,vector<int> U,vector<int> D) { N = P.size(); tim.resize(N); cost.resize(N); ll i; for(i = 0;i < N;i++) { tim[i] = D[i]; cost[i] = U[i]; } for(i = 0;i < N;i++) { DSU[i] = i; fin[i] = 0; st.insert(i); } for(i = 0;i < N;i++) { ll now = *st.begin(); st.erase(now); if(P[now] == -1 || fin[Find(P[now])] == 1) { t += tim[now]; ans += cost[now]*t; fin[now] = 1; continue; } ll top = Find(P[now]); st.erase(top); ans -= cost[top]*tim[now]; cost[top] += cost[now]; tim[top] += tim[now]; st.insert(top); DSU[now] = top; } return ans; }
#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...