oj.uz

Submission #143429

# Submission time Handle Problem Language Result Execution time Memory
143429 2019-08-14T03:53:25 Z model_code Job Scheduling (IOI19_job) Java 11
100 / 100
 2255 ms 115272 KB 
// correct/job-amd.java

import java.util.ArrayList;
import java.util.TreeSet;

class job {
    static final int maxn = 200_000 + 100;
    static long ans = 0L;

    ArrayList<Integer>[] adj = new ArrayList[maxn];
    int[] u = new int[maxn];
    int[] d = new int[maxn];
    int[] p = new int[maxn];

    static class Job implements Comparable<Job> {
        long u, d;
        private Object o;

        Job(int U, int D){
            u = U;
            d = D;
        }
        void merge(Job j) {
            ans += d * j.u;
            u += j.u;
            d += j.d;
        }
        public int compareTo(Job j){ // -1: less that, 0: equal, +1: greater than
            long a = u * j.d;
            long b = j.u * d;
            return Long.compare(a, b);
        }
        public boolean equals(Object o) {
            if(!(o instanceof Job))
                return false;
            Job j = (Job)o;
            return this.compareTo(j) == 0;
        }
    }


    TreeSet<Job>[] se = new TreeSet[maxn];

    int dfs(int v){
        ArrayList<Integer> children = new ArrayList<>();
        int res = v;
        int big = -1; // index in children
        for(int i = 0; i < adj[v].size(); ++ i) {
            int u = adj[v].get(i);
            children.add(dfs(u));
            if (big == -1 || se[children.get(i)].size() > se[children.get(big)].size())
                big = i;
        }
        Job j = new Job(u[v], d[v]);
        if(big == -1){ // leaf
            se[res] = new TreeSet<>();
            se[res].add(j);
            return res;
        }
        res = children.get(big);
        for(int i = 0; i < children.size(); ++ i)
            if(i != big) {
                for(Job jj: se[children.get(i)]) {
                    Job it = se[res].ceiling(jj);
                    if(it != null && jj.compareTo(it) == 0) {
                        jj.merge(it);
                        se[res].remove(it);
                    }
                    se[res].add(jj);
                }
                se[children.get(i)].clear();
            }
        while(!se[res].isEmpty() && j.compareTo(se[res].last()) <= 0) {
            Job last = se[res].last();
            j.merge(last);
            se[res].remove(last);
        }
        se[res].add(j);
        return res;
    }

    public long scheduling_cost(int[] P, int[] U, int[] D) {
        int n = U.length;
        for(int i = 0; i < n; ++ i)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < n; ++ i) {
            u[i] = U[i];
            d[i] = D[i];
            p[i] = P[i];
            ans += (long)u[i] * (long)d[i];
            if (p[i] != -1)
                adj[p[i]].add(i);
        }
        int x = dfs(0);
        long d = 0;
        while(!se[x].isEmpty()) {
            Job j = se[x].last();
            ans += d * j.u;
            d += j.d;
            se[x].remove(j);
        }
        return ans;
    }
}

Compilation message

Note: job.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 13412 KB Output is correct
2 Correct 92 ms 13420 KB Output is correct
3 Correct 93 ms 13688 KB Output is correct
4 Correct 119 ms 15516 KB Output is correct
5 Correct 508 ms 42144 KB Output is correct
6 Correct 1026 ms 63248 KB Output is correct
7 Correct 1575 ms 92504 KB Output is correct
8 Correct 1997 ms 115272 KB Output is correct
9 Correct 2255 ms 108004 KB Output is correct
10 Correct 2017 ms 105688 KB Output is correct
11 Correct 91 ms 13676 KB Output is correct
12 Correct 1978 ms 113356 KB Output is correct
13 Correct 2050 ms 106164 KB Output is correct
14 Correct 2109 ms 107008 KB Output is correct
15 Correct 1951 ms 105112 KB Output is correct
16 Correct 2124 ms 111080 KB Output is correct
17 Correct 2136 ms 105668 KB Output is correct
18 Correct 2122 ms 110316 KB Output is correct
19 Correct 1865 ms 105364 KB Output is correct
20 Correct 2198 ms 112840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13664 KB Output is correct
2 Correct 98 ms 13712 KB Output is correct
3 Correct 101 ms 13736 KB Output is correct
4 Correct 1049 ms 98444 KB Output is correct
5 Correct 1052 ms 98624 KB Output is correct
6 Correct 1051 ms 97640 KB Output is correct
7 Correct 1039 ms 97968 KB Output is correct
8 Correct 999 ms 97132 KB Output is correct
9 Correct 1048 ms 97488 KB Output is correct
10 Correct 1059 ms 97428 KB Output is correct
11 Correct 1014 ms 97688 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13604 KB Output is correct
2 Correct 94 ms 13788 KB Output is correct
3 Correct 95 ms 13796 KB Output is correct
4 Correct 131 ms 15564 KB Output is correct
5 Correct 266 ms 20816 KB Output is correct
6 Correct 1187 ms 104112 KB Output is correct
7 Correct 1189 ms 104404 KB Output is correct
8 Correct 1172 ms 105500 KB Output is correct
9 Correct 1191 ms 104976 KB Output is correct
10 Correct 90 ms 13580 KB Output is correct
11 Correct 158 ms 15796 KB Output is correct
12 Correct 253 ms 20120 KB Output is correct
13 Correct 265 ms 20616 KB Output is correct
14 Correct 1167 ms 104912 KB Output is correct
15 Correct 1145 ms 104784 KB Output is correct
16 Correct 1174 ms 106376 KB Output is correct
17 Correct 1173 ms 105252 KB Output is correct
18 Correct 1169 ms 105164 KB Output is correct
19 Correct 1177 ms 105812 KB Output is correct
20 Correct 1231 ms 105784 KB Output is correct
21 Correct 1147 ms 105116 KB Output is correct
22 Correct 1155 ms 104436 KB Output is correct
23 Correct 1211 ms 105688 KB Output is correct
24 Correct 1203 ms 105640 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13524 KB Output is correct
2 Correct 1263 ms 92024 KB Output is correct
3 Correct 1300 ms 95512 KB Output is correct
4 Correct 1260 ms 93996 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 13556 KB Output is correct
2 Correct 94 ms 13708 KB Output is correct
3 Correct 104 ms 13800 KB Output is correct
4 Correct 106 ms 13844 KB Output is correct
5 Correct 101 ms 13760 KB Output is correct
6 Correct 89 ms 13576 KB Output is correct
7 Correct 94 ms 13688 KB Output is correct
8 Correct 96 ms 13844 KB Output is correct
9 Correct 102 ms 13712 KB Output is correct
10 Correct 101 ms 13736 KB Output is correct
11 Correct 109 ms 13708 KB Output is correct
12 Correct 104 ms 13828 KB Output is correct
13 Correct 109 ms 13888 KB Output is correct
14 Correct 108 ms 13820 KB Output is correct
15 Correct 101 ms 13828 KB Output is correct
16 Correct 101 ms 13856 KB Output is correct
17 Correct 109 ms 13792 KB Output is correct

Subtask #6
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 13412 KB Output is correct
2 Correct 92 ms 13420 KB Output is correct
3 Correct 93 ms 13688 KB Output is correct
4 Correct 119 ms 15516 KB Output is correct
5 Correct 508 ms 42144 KB Output is correct
6 Correct 1026 ms 63248 KB Output is correct
7 Correct 1575 ms 92504 KB Output is correct
8 Correct 1997 ms 115272 KB Output is correct
9 Correct 2255 ms 108004 KB Output is correct
10 Correct 2017 ms 105688 KB Output is correct
11 Correct 91 ms 13676 KB Output is correct
12 Correct 1978 ms 113356 KB Output is correct
13 Correct 2050 ms 106164 KB Output is correct
14 Correct 2109 ms 107008 KB Output is correct
15 Correct 1951 ms 105112 KB Output is correct
16 Correct 2124 ms 111080 KB Output is correct
17 Correct 2136 ms 105668 KB Output is correct
18 Correct 2122 ms 110316 KB Output is correct
19 Correct 1865 ms 105364 KB Output is correct
20 Correct 2198 ms 112840 KB Output is correct
21 Correct 90 ms 13664 KB Output is correct
22 Correct 98 ms 13712 KB Output is correct
23 Correct 101 ms 13736 KB Output is correct
24 Correct 1049 ms 98444 KB Output is correct
25 Correct 1052 ms 98624 KB Output is correct
26 Correct 1051 ms 97640 KB Output is correct
27 Correct 1039 ms 97968 KB Output is correct
28 Correct 999 ms 97132 KB Output is correct
29 Correct 1048 ms 97488 KB Output is correct
30 Correct 1059 ms 97428 KB Output is correct
31 Correct 1014 ms 97688 KB Output is correct
32 Correct 90 ms 13604 KB Output is correct
33 Correct 94 ms 13788 KB Output is correct
34 Correct 95 ms 13796 KB Output is correct
35 Correct 131 ms 15564 KB Output is correct
36 Correct 266 ms 20816 KB Output is correct
37 Correct 1187 ms 104112 KB Output is correct
38 Correct 1189 ms 104404 KB Output is correct
39 Correct 1172 ms 105500 KB Output is correct
40 Correct 1191 ms 104976 KB Output is correct
41 Correct 90 ms 13580 KB Output is correct
42 Correct 158 ms 15796 KB Output is correct
43 Correct 253 ms 20120 KB Output is correct
44 Correct 265 ms 20616 KB Output is correct
45 Correct 1167 ms 104912 KB Output is correct
46 Correct 1145 ms 104784 KB Output is correct
47 Correct 1174 ms 106376 KB Output is correct
48 Correct 1173 ms 105252 KB Output is correct
49 Correct 1169 ms 105164 KB Output is correct
50 Correct 1177 ms 105812 KB Output is correct
51 Correct 1231 ms 105784 KB Output is correct
52 Correct 1147 ms 105116 KB Output is correct
53 Correct 1155 ms 104436 KB Output is correct
54 Correct 1211 ms 105688 KB Output is correct
55 Correct 1203 ms 105640 KB Output is correct
56 Correct 90 ms 13524 KB Output is correct
57 Correct 1263 ms 92024 KB Output is correct
58 Correct 1300 ms 95512 KB Output is correct
59 Correct 1260 ms 93996 KB Output is correct
60 Correct 91 ms 13556 KB Output is correct
61 Correct 94 ms 13708 KB Output is correct
62 Correct 104 ms 13800 KB Output is correct
63 Correct 106 ms 13844 KB Output is correct
64 Correct 101 ms 13760 KB Output is correct
65 Correct 89 ms 13576 KB Output is correct
66 Correct 94 ms 13688 KB Output is correct
67 Correct 96 ms 13844 KB Output is correct
68 Correct 102 ms 13712 KB Output is correct
69 Correct 101 ms 13736 KB Output is correct
70 Correct 109 ms 13708 KB Output is correct
71 Correct 104 ms 13828 KB Output is correct
72 Correct 109 ms 13888 KB Output is correct
73 Correct 108 ms 13820 KB Output is correct
74 Correct 101 ms 13828 KB Output is correct
75 Correct 101 ms 13856 KB Output is correct
76 Correct 109 ms 13792 KB Output is correct
77 Correct 91 ms 13688 KB Output is correct
78 Correct 91 ms 13520 KB Output is correct
79 Correct 91 ms 13600 KB Output is correct
80 Correct 90 ms 13692 KB Output is correct
81 Correct 101 ms 13436 KB Output is correct
82 Correct 94 ms 13632 KB Output is correct
83 Correct 96 ms 13828 KB Output is correct
84 Correct 91 ms 13688 KB Output is correct
85 Correct 91 ms 13668 KB Output is correct
86 Correct 92 ms 13612 KB Output is correct
87 Correct 94 ms 13576 KB Output is correct
88 Correct 208 ms 20044 KB Output is correct
89 Correct 207 ms 21036 KB Output is correct
90 Correct 231 ms 21244 KB Output is correct
91 Correct 515 ms 40588 KB Output is correct
92 Correct 832 ms 75076 KB Output is correct
93 Correct 1377 ms 95612 KB Output is correct
94 Correct 1377 ms 95632 KB Output is correct
95 Correct 1360 ms 95868 KB Output is correct
96 Correct 1335 ms 95452 KB Output is correct
97 Correct 1365 ms 92128 KB Output is correct
98 Correct 1317 ms 95792 KB Output is correct
99 Correct 1343 ms 91864 KB Output is correct
100 Correct 1298 ms 90820 KB Output is correct
101 Correct 1207 ms 93608 KB Output is correct
102 Correct 1501 ms 96596 KB Output is correct
103 Correct 1228 ms 94452 KB Output is correct
104 Correct 1094 ms 91748 KB Output is correct
105 Correct 908 ms 83712 KB Output is correct
106 Correct 1477 ms 101896 KB Output is correct