oj.uz

Submission #155079

# Submission time Handle Problem Language Result Execution time Memory
155079 2019-09-26T07:22:36 Z neki Job Scheduling (IOI19_job) C++14
0 / 100
 10 ms 9720 KB 
#include "job.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i=a;i<b;i++)
typedef long long ll;

struct t{
  vector<ll> chs;ll u, d, id;
  bool operator<(const t& oth) const {return u * oth.d<oth.u * d;}
};

t ts[200100];
int act[200100];
 
ll scheduling_cost(vector<int> P, vector<int> U, vector<int> D) {
  ll n=P.size(), ans=0;
  P.push_back(0), U.push_back(0), D.push_back(0);P[0]=n;
  loop(i, 1, n) ts[P[i]].chs.push_back(i);
  loop(i, 0, n) ts[i].u=U[i], ts[i].d=D[i], ts[i].id=i, act[i]=1;
  priority_queue<t> q;
  loop(i, 0, n) q.push(ts[i]);
  while(q.size()){
    t nek=q.top(); q.pop();
    if(act[nek.id]&&nek.u==ts[nek.id].u&&nek.d==ts[nek.id].d){
      act[nek.id]=0;
      ts[P[nek.id]].d+=ts[nek.id].d;
      ans+=ts[P[nek.id]].d * ts[nek.id].u;
      ts[P[nek.id]].u+=ts[nek.id].u;
      for(auto&& j : ts[nek.id].chs) P[j]=P[nek.id];
      if(nek.id!=n&&act[P[nek.id]]) q.push(ts[P[nek.id]]);
    }
  }
  return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -