Submission #318988

#	Time	Username	Problem	Language	Result	Execution time	Memory
318988		alextodoran	Job Scheduling (IOI19_job)	C++17	100 / 100	313 ms	67684 KiB

job

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "job.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200002;

int n;

struct Cost
{
   int d, u;
};

Cost cost[N_MAX];

int parent[N_MAX];

vector <int> sons[N_MAX];

bool operator < (const Cost &a, const Cost &b)
{
   return (ll)a.d * b.u < (ll)b.d * a.u;
}

struct Node
{
   int u;
   Cost c;
};

bool operator < (const Node &u, const Node &v)
{
   return make_pair(u.c, u.u) < make_pair(v.c, v.u);
}

ll answer = 0;
set <Node> notJoined[N_MAX];

void mergeSets (int u, int v)
{
   answer += (ll)cost[u].d * cost[v].u;
   cost[u].d += cost[v].d;
   cost[u].u += cost[v].u;
   set <Node> &in = notJoined[u];
   set <Node> &from = notJoined[v];

   if(in.size() < from.size())
       swap(in, from);
   while(from.empty() == false)
   {
       in.insert(*from.begin());
       from.erase(from.begin());
   }
}

void dfs (int u)
{
   for(int v : sons[u])
   {
       dfs(v);
       notJoined[u].insert(Node{v, cost[v]});
   }
   while (!notJoined[u].empty())
   {
       int v = notJoined[u].begin()->u;
       if(cost[u] < cost[v])
           break;
       notJoined[u].erase(notJoined[u].begin());
       mergeSets(u, v);
   }
}

int order[N_MAX];

int curr;

ll scheduling_cost (vector <int> p, vector <int> u, vector <int> d)
{
   n = p.size();
   for(int i = 1; i <= n; i++)
   {
       parent[i] = p[i - 1] + 1;
       cost[i] = Cost{d[i - 1], u[i - 1]};
       answer += (ll)cost[i].u * cost[i].d;
   }
   for(int i = 2; i <= n; i++)
       sons[parent[i]].push_back(i);
   dfs(1);
   while(!notJoined[1].empty())
   {
       int v = notJoined[1].begin()->u;
       notJoined[1].erase(notJoined[1].begin());
       mergeSets(1, v);
   }
   return answer;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37