# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

143470 | 2019-08-14T08:23:12 Z | dolphingarlic | Job Scheduling (IOI19_job) | C++14 | 262 ms | 27564 KB |

#include "job.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int mxN = 2e5; int n, nxt[mxN], ta[mxN]; vector<int> o; ll u2[mxN], d2[mxN]; struct cmp { bool operator()(const int &a, const int &b) { return d2[a] * u2[b] > d2[b] * u2[a]; } }; priority_queue<int, vector<int>, cmp> c[mxN]; void dfs(int u) { o.push_back(u); for (; c[u].size(); c[u].pop()) dfs(c[u].top()); } ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) { n = p.size(); memset(nxt, -1, 4 * n); iota(ta, ta + n, 0); for (int i = n - 1; ~i; --i) { u2[i] = u[i]; d2[i] = d[i]; while (c[i].size()) { int u = c[i].top(); if (cmp()(u, i)) break; c[i].pop(); nxt[ta[i]] = u; ta[i] = ta[u]; u2[i] += u2[u]; d2[i] += d2[u]; if (c[i].size() < c[u].size()) swap(c[i], c[u]); for (; c[u].size(); c[u].pop()) c[i].push(c[u].top()); } if (i) c[p[i]].push(i); } dfs(0); sort(o.begin(), o.end(), cmp()); ll t = 0, ans = 0; for (int i = o.size() - 1; ~i; --i) { for (int j = o[i]; ~j; j = nxt[j]) { t += d[j]; ans += t * u[j]; } } return ans; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 8 ms | 6648 KB | Output is correct |

2 | Correct | 7 ms | 6648 KB | Output is correct |

3 | Correct | 7 ms | 6648 KB | Output is correct |

4 | Correct | 8 ms | 6648 KB | Output is correct |

5 | Correct | 32 ms | 10488 KB | Output is correct |

6 | Correct | 58 ms | 14456 KB | Output is correct |

7 | Correct | 81 ms | 18296 KB | Output is correct |

8 | Correct | 107 ms | 22184 KB | Output is correct |

9 | Correct | 110 ms | 22332 KB | Output is correct |

10 | Correct | 109 ms | 22264 KB | Output is correct |

11 | Correct | 7 ms | 6648 KB | Output is correct |

12 | Correct | 107 ms | 22264 KB | Output is correct |

13 | Correct | 105 ms | 22264 KB | Output is correct |

14 | Correct | 107 ms | 22264 KB | Output is correct |

15 | Correct | 112 ms | 22264 KB | Output is correct |

16 | Correct | 107 ms | 22364 KB | Output is correct |

17 | Correct | 112 ms | 22328 KB | Output is correct |

18 | Correct | 107 ms | 22264 KB | Output is correct |

19 | Correct | 104 ms | 22264 KB | Output is correct |

20 | Correct | 118 ms | 27564 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 9 ms | 6648 KB | Output is correct |

2 | Correct | 7 ms | 6648 KB | Output is correct |

3 | Correct | 8 ms | 6648 KB | Output is correct |

4 | Correct | 219 ms | 18288 KB | Output is correct |

5 | Correct | 224 ms | 18352 KB | Output is correct |

6 | Correct | 222 ms | 18368 KB | Output is correct |

7 | Correct | 224 ms | 18284 KB | Output is correct |

8 | Correct | 224 ms | 18284 KB | Output is correct |

9 | Correct | 205 ms | 18284 KB | Output is correct |

10 | Correct | 232 ms | 18428 KB | Output is correct |

11 | Correct | 225 ms | 18464 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 7 ms | 6648 KB | Output is correct |

2 | Correct | 7 ms | 6648 KB | Output is correct |

3 | Correct | 7 ms | 6648 KB | Output is correct |

4 | Correct | 8 ms | 6648 KB | Output is correct |

5 | Correct | 14 ms | 7160 KB | Output is correct |

6 | Correct | 220 ms | 18256 KB | Output is correct |

7 | Correct | 219 ms | 18284 KB | Output is correct |

8 | Correct | 237 ms | 18284 KB | Output is correct |

9 | Correct | 220 ms | 18384 KB | Output is correct |

10 | Correct | 9 ms | 6520 KB | Output is correct |

11 | Correct | 9 ms | 6648 KB | Output is correct |

12 | Correct | 15 ms | 7160 KB | Output is correct |

13 | Correct | 14 ms | 7160 KB | Output is correct |

14 | Correct | 232 ms | 18284 KB | Output is correct |

15 | Correct | 220 ms | 18284 KB | Output is correct |

16 | Correct | 218 ms | 18308 KB | Output is correct |

17 | Correct | 216 ms | 18312 KB | Output is correct |

18 | Correct | 220 ms | 18372 KB | Output is correct |

19 | Correct | 215 ms | 18584 KB | Output is correct |

20 | Correct | 226 ms | 18412 KB | Output is correct |

21 | Correct | 223 ms | 18292 KB | Output is correct |

22 | Correct | 222 ms | 18372 KB | Output is correct |

23 | Correct | 223 ms | 18288 KB | Output is correct |

24 | Correct | 262 ms | 18412 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 7 ms | 6676 KB | Output is correct |

2 | Correct | 108 ms | 22348 KB | Output is correct |

3 | Correct | 108 ms | 22264 KB | Output is correct |

4 | Correct | 108 ms | 22236 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 7 ms | 6648 KB | Output is correct |

2 | Correct | 7 ms | 6524 KB | Output is correct |

3 | Correct | 7 ms | 6648 KB | Output is correct |

4 | Correct | 10 ms | 6648 KB | Output is correct |

5 | Correct | 7 ms | 6648 KB | Output is correct |

6 | Correct | 7 ms | 6648 KB | Output is correct |

7 | Correct | 9 ms | 6648 KB | Output is correct |

8 | Correct | 7 ms | 6648 KB | Output is correct |

9 | Correct | 7 ms | 6648 KB | Output is correct |

10 | Correct | 7 ms | 6648 KB | Output is correct |

11 | Correct | 7 ms | 6648 KB | Output is correct |

12 | Correct | 7 ms | 6648 KB | Output is correct |

13 | Correct | 7 ms | 6648 KB | Output is correct |

14 | Correct | 7 ms | 6648 KB | Output is correct |

15 | Correct | 7 ms | 6648 KB | Output is correct |

16 | Correct | 7 ms | 6648 KB | Output is correct |

17 | Correct | 7 ms | 6648 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 8 ms | 6648 KB | Output is correct |

2 | Correct | 7 ms | 6648 KB | Output is correct |

3 | Correct | 7 ms | 6648 KB | Output is correct |

4 | Correct | 8 ms | 6648 KB | Output is correct |

5 | Correct | 32 ms | 10488 KB | Output is correct |

6 | Correct | 58 ms | 14456 KB | Output is correct |

7 | Correct | 81 ms | 18296 KB | Output is correct |

8 | Correct | 107 ms | 22184 KB | Output is correct |

9 | Correct | 110 ms | 22332 KB | Output is correct |

10 | Correct | 109 ms | 22264 KB | Output is correct |

11 | Correct | 7 ms | 6648 KB | Output is correct |

12 | Correct | 107 ms | 22264 KB | Output is correct |

13 | Correct | 105 ms | 22264 KB | Output is correct |

14 | Correct | 107 ms | 22264 KB | Output is correct |

15 | Correct | 112 ms | 22264 KB | Output is correct |

16 | Correct | 107 ms | 22364 KB | Output is correct |

17 | Correct | 112 ms | 22328 KB | Output is correct |

18 | Correct | 107 ms | 22264 KB | Output is correct |

19 | Correct | 104 ms | 22264 KB | Output is correct |

20 | Correct | 118 ms | 27564 KB | Output is correct |

21 | Correct | 9 ms | 6648 KB | Output is correct |

22 | Correct | 7 ms | 6648 KB | Output is correct |

23 | Correct | 8 ms | 6648 KB | Output is correct |

24 | Correct | 219 ms | 18288 KB | Output is correct |

25 | Correct | 224 ms | 18352 KB | Output is correct |

26 | Correct | 222 ms | 18368 KB | Output is correct |

27 | Correct | 224 ms | 18284 KB | Output is correct |

28 | Correct | 224 ms | 18284 KB | Output is correct |

29 | Correct | 205 ms | 18284 KB | Output is correct |

30 | Correct | 232 ms | 18428 KB | Output is correct |

31 | Correct | 225 ms | 18464 KB | Output is correct |

32 | Correct | 7 ms | 6648 KB | Output is correct |

33 | Correct | 7 ms | 6648 KB | Output is correct |

34 | Correct | 7 ms | 6648 KB | Output is correct |

35 | Correct | 8 ms | 6648 KB | Output is correct |

36 | Correct | 14 ms | 7160 KB | Output is correct |

37 | Correct | 220 ms | 18256 KB | Output is correct |

38 | Correct | 219 ms | 18284 KB | Output is correct |

39 | Correct | 237 ms | 18284 KB | Output is correct |

40 | Correct | 220 ms | 18384 KB | Output is correct |

41 | Correct | 9 ms | 6520 KB | Output is correct |

42 | Correct | 9 ms | 6648 KB | Output is correct |

43 | Correct | 15 ms | 7160 KB | Output is correct |

44 | Correct | 14 ms | 7160 KB | Output is correct |

45 | Correct | 232 ms | 18284 KB | Output is correct |

46 | Correct | 220 ms | 18284 KB | Output is correct |

47 | Correct | 218 ms | 18308 KB | Output is correct |

48 | Correct | 216 ms | 18312 KB | Output is correct |

49 | Correct | 220 ms | 18372 KB | Output is correct |

50 | Correct | 215 ms | 18584 KB | Output is correct |

51 | Correct | 226 ms | 18412 KB | Output is correct |

52 | Correct | 223 ms | 18292 KB | Output is correct |

53 | Correct | 222 ms | 18372 KB | Output is correct |

54 | Correct | 223 ms | 18288 KB | Output is correct |

55 | Correct | 262 ms | 18412 KB | Output is correct |

56 | Correct | 7 ms | 6676 KB | Output is correct |

57 | Correct | 108 ms | 22348 KB | Output is correct |

58 | Correct | 108 ms | 22264 KB | Output is correct |

59 | Correct | 108 ms | 22236 KB | Output is correct |

60 | Correct | 7 ms | 6648 KB | Output is correct |

61 | Correct | 7 ms | 6524 KB | Output is correct |

62 | Correct | 7 ms | 6648 KB | Output is correct |

63 | Correct | 10 ms | 6648 KB | Output is correct |

64 | Correct | 7 ms | 6648 KB | Output is correct |

65 | Correct | 7 ms | 6648 KB | Output is correct |

66 | Correct | 9 ms | 6648 KB | Output is correct |

67 | Correct | 7 ms | 6648 KB | Output is correct |

68 | Correct | 7 ms | 6648 KB | Output is correct |

69 | Correct | 7 ms | 6648 KB | Output is correct |

70 | Correct | 7 ms | 6648 KB | Output is correct |

71 | Correct | 7 ms | 6648 KB | Output is correct |

72 | Correct | 7 ms | 6648 KB | Output is correct |

73 | Correct | 7 ms | 6648 KB | Output is correct |

74 | Correct | 7 ms | 6648 KB | Output is correct |

75 | Correct | 7 ms | 6648 KB | Output is correct |

76 | Correct | 7 ms | 6648 KB | Output is correct |

77 | Correct | 8 ms | 6648 KB | Output is correct |

78 | Correct | 7 ms | 6648 KB | Output is correct |

79 | Correct | 7 ms | 6520 KB | Output is correct |

80 | Correct | 7 ms | 6648 KB | Output is correct |

81 | Correct | 7 ms | 6648 KB | Output is correct |

82 | Correct | 7 ms | 6648 KB | Output is correct |

83 | Correct | 7 ms | 6648 KB | Output is correct |

84 | Correct | 7 ms | 6648 KB | Output is correct |

85 | Correct | 7 ms | 6520 KB | Output is correct |

86 | Correct | 9 ms | 6648 KB | Output is correct |

87 | Correct | 7 ms | 6648 KB | Output is correct |

88 | Correct | 10 ms | 6904 KB | Output is correct |

89 | Correct | 13 ms | 7160 KB | Output is correct |

90 | Correct | 16 ms | 7288 KB | Output is correct |

91 | Correct | 49 ms | 10104 KB | Output is correct |

92 | Correct | 104 ms | 13524 KB | Output is correct |

93 | Correct | 197 ms | 20320 KB | Output is correct |

94 | Correct | 191 ms | 20340 KB | Output is correct |

95 | Correct | 193 ms | 20344 KB | Output is correct |

96 | Correct | 201 ms | 20352 KB | Output is correct |

97 | Correct | 183 ms | 19700 KB | Output is correct |

98 | Correct | 175 ms | 20704 KB | Output is correct |

99 | Correct | 177 ms | 19704 KB | Output is correct |

100 | Correct | 198 ms | 20308 KB | Output is correct |

101 | Correct | 165 ms | 20980 KB | Output is correct |

102 | Correct | 196 ms | 20420 KB | Output is correct |

103 | Correct | 172 ms | 19940 KB | Output is correct |

104 | Correct | 157 ms | 20472 KB | Output is correct |

105 | Correct | 132 ms | 20604 KB | Output is correct |

106 | Correct | 174 ms | 18416 KB | Output is correct |