Submission #211340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211340	2020-03-20T06:30:48 Z	eric_xiao	Job Scheduling (IOI19_job)	C++14	7 / 100	490 ms	21472 KB

#include<bits/stdc++.h>
#define ll long long

using namespace std;
ll N,t,ans;
ll DSU[300009],fin[300009];
vector<int> 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();
    cost = U;
    tim = D;
    ll 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;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Incorrect	4 ms	384 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	236 ms	20856 KB	Output is correct
5	Correct	237 ms	20856 KB	Output is correct
6	Correct	252 ms	20856 KB	Output is correct
7	Correct	237 ms	20856 KB	Output is correct
8	Correct	241 ms	20984 KB	Output is correct
9	Correct	255 ms	20856 KB	Output is correct
10	Correct	238 ms	20856 KB	Output is correct
11	Correct	251 ms	20984 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	12 ms	1280 KB	Output is correct
6	Incorrect	222 ms	21472 KB	Output isn't correct
7	Halted	0 ms	0 KB	-