oj.uz

Submission #245742

# Submission time Handle Problem Language Result Execution time Memory
245742 2020-07-07T10:13:26 Z quocnguyen1012 Job Scheduling (IOI19_job) C++14
26 / 100
 740 ms 20728 KB 
#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
  {
    return 1ll * cost[a] * tim[b] > 1ll * cost[b] * tim[a];
  }
};
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

Subtask #1
5.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 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 89 ms 5272 KB Output is correct
6 Correct 231 ms 10104 KB Output is correct
7 Correct 467 ms 15096 KB Output is correct
8 Correct 740 ms 19956 KB Output is correct
9 Correct 731 ms 19956 KB Output is correct
10 Correct 679 ms 19948 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 647 ms 19972 KB Output is correct
13 Correct 363 ms 19952 KB Output is correct
14 Correct 396 ms 20600 KB Output is correct
15 Correct 272 ms 19960 KB Output is correct
16 Correct 302 ms 20604 KB Output is correct
17 Correct 673 ms 19960 KB Output is correct
18 Correct 598 ms 19960 KB Output is correct
19 Correct 171 ms 19960 KB Output is correct
20 Correct 159 ms 20728 KB Output is correct

Subtask #2
0 / 7.0

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

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 Incorrect 13 ms 1152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 655 ms 16816 KB Output is correct
3 Correct 634 ms 20080 KB Output is correct
4 Incorrect 673 ms 19960 KB Output isn't correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 436 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct

Subtask #6
0 / 37.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 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 89 ms 5272 KB Output is correct
6 Correct 231 ms 10104 KB Output is correct
7 Correct 467 ms 15096 KB Output is correct
8 Correct 740 ms 19956 KB Output is correct
9 Correct 731 ms 19956 KB Output is correct
10 Correct 679 ms 19948 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 647 ms 19972 KB Output is correct
13 Correct 363 ms 19952 KB Output is correct
14 Correct 396 ms 20600 KB Output is correct
15 Correct 272 ms 19960 KB Output is correct
16 Correct 302 ms 20604 KB Output is correct
17 Correct 673 ms 19960 KB Output is correct
18 Correct 598 ms 19960 KB Output is correct
19 Correct 171 ms 19960 KB Output is correct
20 Correct 159 ms 20728 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Incorrect 5 ms 384 KB Output isn't correct
24 Halted 0 ms 0 KB -