oj.uz

Submission #647257

# Submission time Handle Problem Language Result Execution time Memory
647257 2022-10-02T05:04:12 Z atom Fireworks (APIO16_fireworks) Java 11
55 / 100
 2000 ms 333756 KB 
import java.io.*;
import java.util.*;
// @Jasper

public class fireworks {
    static long LINF = (long) 1e18 + 5;
    static int INF = (int) 1e9 + 5;
    static int MOD = (int) 1e9 + 7;
    static int MAX = (int) 3e5 + 5;

    static long n, m, ans = 0, a, b;
    static long[] plague = new long [MAX];
    static long[] root = new long [MAX];

    static List <Integer>[] edges = new List[MAX];
    static PriorityQueue <Long>[] q = new PriorityQueue [MAX];

    public static void dfs(int u){
        root[u] = u;
        if (u > n){
            q[u].add(plague[u]);
            q[u].add(plague[u]);
            return;
        }

        for (int v : edges[u]){
            dfs(v);
            if (q[(int) root[v]].size() > q[(int) root[u]].size())
                root[u] = root[v];
        }

        for (int v : edges[u]){
            if (root[u] != root[v]){
                while (q[(int) root[v]].size() > 0){
                    long tmp = q[(int) root[v]].poll();
                    q[(int) root[u]].add(tmp);
                }
            }
        }
        for (int i = 1; i < edges[u].size(); i++) 
            q[(int) root[u]].poll();

        // System.out.println(a + " " + b);
        a = q[(int) root[u]].poll();
        b = q[(int) root[u]].poll();
        a += plague[u];
        b += plague[u];
        q[(int) root[u]].add(b);
        q[(int) root[u]].add(a);
    }


    //------------------Solution------------------------------------------------  
    private static void run_case() throws Exception {
        n = io.nextInt();
        m = io.nextInt();
        m += n;
        ans = 0; 
        for (int i = 0; i < MAX; ++i){
            edges[i] = new ArrayList <Integer> (); 
            q[i] = new PriorityQueue <Long> ((x, y) -> Long.compare(y, x));
        }
        for (int i = 2; i <= m; i++){
            a = io.nextInt();
            b = io.nextInt();
            edges[(int) a].add(i);
            plague[i] = b;
            ans += b;
        }
        // System.out.println(ans);
        
        dfs(1);
       
        // System.out.println(a + " " + b);

        long tmp = q[(int)root[1]].poll();
        a = q[(int)root[1]].peek();
        q[(int)root[1]].add((long) 0);
        b = 0;
        
        while (q[(int) root[1]].size() > 0){
            ans -= (a - q[(int) root[1]].peek()) * b;
            b++;
            a = q[(int) root[1]].poll();
        }
        System.out.println(ans);
    }
    
    public static void main(String[] args) throws Exception {
        int Test = 1;
       // Test = io.nextInt();
        for (int i = 1; i <= Test; i++){
            
            run_case();
        }
        io.close();
    }


    //-----------PrintWriter for faster output---------------------------------
    public static FastIO io = new FastIO();

    static void sort(int[] a) {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : a) l.add(i);
        Collections.sort(l);
        for (int i = 0; i < a.length; i++) a[i] = l.get(i);
    }

        public static void swap(int data[], int left, int right) {
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }

        public static void reverse(int data[], int left, int right){
            while (left < right) {
                int temp = data[left];
                data[left++] = data[right];
                data[right--] = temp;
            }
        }
 
        public static boolean nextPermutation(int data[]){
            if (data.length <= 1)
                return false;
 
            int last = data.length - 2;
            while (last >= 0) {
                if (data[last] < data[last + 1]) 
                    break;
                last--;
         }
            if (last < 0)
                return false;
 
            int nextGreater = data.length - 1;
 
            for (int i = data.length - 1; i > last; i--) {
                if (data[i] > data[last]) {
                    nextGreater = i;
                    break;
                }
            }
 
            swap(data, nextGreater, last);
            reverse(data, last + 1, data.length - 1);
 
            return true;
        }
    //-----------MyScanner class for faster input----------
    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar, numChars;

        // standard input
        public FastIO() {
            this(System.in, System.out);
        }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public String nextLine() {
            int c;
            do {
                c = nextByte();
            } while (c < '\n');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > '\n');
            return res.toString();
        }

        public int nextInt() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public long nextLong() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }


        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    //--------------------------------------------------------
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54736 KB Output is correct
2 Correct 210 ms 54312 KB Output is correct
3 Correct 199 ms 54348 KB Output is correct
4 Correct 218 ms 54300 KB Output is correct
5 Correct 195 ms 54464 KB Output is correct
6 Correct 191 ms 54488 KB Output is correct
7 Correct 206 ms 54460 KB Output is correct
8 Correct 200 ms 54424 KB Output is correct
9 Correct 207 ms 54336 KB Output is correct
10 Correct 193 ms 54528 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54596 KB Output is correct
2 Correct 203 ms 54396 KB Output is correct
3 Correct 198 ms 54336 KB Output is correct
4 Correct 200 ms 54276 KB Output is correct
5 Correct 213 ms 54304 KB Output is correct
6 Correct 198 ms 54472 KB Output is correct
7 Correct 212 ms 54360 KB Output is correct
8 Correct 221 ms 54232 KB Output is correct
9 Correct 207 ms 54320 KB Output is correct
10 Correct 222 ms 54484 KB Output is correct
11 Correct 211 ms 54292 KB Output is correct
12 Correct 203 ms 54316 KB Output is correct
13 Correct 214 ms 54280 KB Output is correct
14 Correct 200 ms 54640 KB Output is correct
15 Correct 202 ms 54492 KB Output is correct
16 Correct 223 ms 54416 KB Output is correct
17 Correct 201 ms 54372 KB Output is correct
18 Correct 201 ms 54404 KB Output is correct
19 Correct 208 ms 54460 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54736 KB Output is correct
2 Correct 210 ms 54312 KB Output is correct
3 Correct 199 ms 54348 KB Output is correct
4 Correct 218 ms 54300 KB Output is correct
5 Correct 195 ms 54464 KB Output is correct
6 Correct 191 ms 54488 KB Output is correct
7 Correct 206 ms 54460 KB Output is correct
8 Correct 200 ms 54424 KB Output is correct
9 Correct 207 ms 54336 KB Output is correct
10 Correct 193 ms 54528 KB Output is correct
11 Correct 195 ms 54596 KB Output is correct
12 Correct 203 ms 54396 KB Output is correct
13 Correct 198 ms 54336 KB Output is correct
14 Correct 200 ms 54276 KB Output is correct
15 Correct 213 ms 54304 KB Output is correct
16 Correct 198 ms 54472 KB Output is correct
17 Correct 212 ms 54360 KB Output is correct
18 Correct 221 ms 54232 KB Output is correct
19 Correct 207 ms 54320 KB Output is correct
20 Correct 222 ms 54484 KB Output is correct
21 Correct 211 ms 54292 KB Output is correct
22 Correct 203 ms 54316 KB Output is correct
23 Correct 214 ms 54280 KB Output is correct
24 Correct 200 ms 54640 KB Output is correct
25 Correct 202 ms 54492 KB Output is correct
26 Correct 223 ms 54416 KB Output is correct
27 Correct 201 ms 54372 KB Output is correct
28 Correct 201 ms 54404 KB Output is correct
29 Correct 208 ms 54460 KB Output is correct
30 Correct 203 ms 54328 KB Output is correct
31 Correct 223 ms 54484 KB Output is correct
32 Correct 250 ms 55076 KB Output is correct
33 Correct 327 ms 63820 KB Output is correct
34 Correct 336 ms 64140 KB Output is correct
35 Correct 339 ms 63988 KB Output is correct
36 Correct 341 ms 63860 KB Output is correct
37 Correct 349 ms 63772 KB Output is correct
38 Correct 345 ms 63972 KB Output is correct
39 Correct 360 ms 63740 KB Output is correct
40 Correct 266 ms 55260 KB Output is correct
41 Correct 336 ms 61792 KB Output is correct
42 Correct 312 ms 61248 KB Output is correct
43 Correct 307 ms 56460 KB Output is correct
44 Correct 373 ms 64232 KB Output is correct
45 Correct 424 ms 64128 KB Output is correct
46 Correct 334 ms 63456 KB Output is correct
47 Correct 326 ms 63668 KB Output is correct
48 Correct 344 ms 63704 KB Output is correct
49 Correct 328 ms 63636 KB Output is correct
50 Correct 324 ms 56320 KB Output is correct
51 Correct 290 ms 56360 KB Output is correct
52 Correct 337 ms 60172 KB Output is correct
53 Correct 412 ms 63684 KB Output is correct
54 Correct 279 ms 54596 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54736 KB Output is correct
2 Correct 210 ms 54312 KB Output is correct
3 Correct 199 ms 54348 KB Output is correct
4 Correct 218 ms 54300 KB Output is correct
5 Correct 195 ms 54464 KB Output is correct
6 Correct 191 ms 54488 KB Output is correct
7 Correct 206 ms 54460 KB Output is correct
8 Correct 200 ms 54424 KB Output is correct
9 Correct 207 ms 54336 KB Output is correct
10 Correct 193 ms 54528 KB Output is correct
11 Correct 195 ms 54596 KB Output is correct
12 Correct 203 ms 54396 KB Output is correct
13 Correct 198 ms 54336 KB Output is correct
14 Correct 200 ms 54276 KB Output is correct
15 Correct 213 ms 54304 KB Output is correct
16 Correct 198 ms 54472 KB Output is correct
17 Correct 212 ms 54360 KB Output is correct
18 Correct 221 ms 54232 KB Output is correct
19 Correct 207 ms 54320 KB Output is correct
20 Correct 222 ms 54484 KB Output is correct
21 Correct 211 ms 54292 KB Output is correct
22 Correct 203 ms 54316 KB Output is correct
23 Correct 214 ms 54280 KB Output is correct
24 Correct 200 ms 54640 KB Output is correct
25 Correct 202 ms 54492 KB Output is correct
26 Correct 223 ms 54416 KB Output is correct
27 Correct 201 ms 54372 KB Output is correct
28 Correct 201 ms 54404 KB Output is correct
29 Correct 208 ms 54460 KB Output is correct
30 Correct 203 ms 54328 KB Output is correct
31 Correct 223 ms 54484 KB Output is correct
32 Correct 250 ms 55076 KB Output is correct
33 Correct 327 ms 63820 KB Output is correct
34 Correct 336 ms 64140 KB Output is correct
35 Correct 339 ms 63988 KB Output is correct
36 Correct 341 ms 63860 KB Output is correct
37 Correct 349 ms 63772 KB Output is correct
38 Correct 345 ms 63972 KB Output is correct
39 Correct 360 ms 63740 KB Output is correct
40 Correct 266 ms 55260 KB Output is correct
41 Correct 336 ms 61792 KB Output is correct
42 Correct 312 ms 61248 KB Output is correct
43 Correct 307 ms 56460 KB Output is correct
44 Correct 373 ms 64232 KB Output is correct
45 Correct 424 ms 64128 KB Output is correct
46 Correct 334 ms 63456 KB Output is correct
47 Correct 326 ms 63668 KB Output is correct
48 Correct 344 ms 63704 KB Output is correct
49 Correct 328 ms 63636 KB Output is correct
50 Correct 324 ms 56320 KB Output is correct
51 Correct 290 ms 56360 KB Output is correct
52 Correct 337 ms 60172 KB Output is correct
53 Correct 412 ms 63684 KB Output is correct
54 Correct 279 ms 54596 KB Output is correct
55 Correct 426 ms 63872 KB Output is correct
56 Correct 463 ms 69232 KB Output is correct
57 Correct 570 ms 89156 KB Output is correct
58 Correct 563 ms 90196 KB Output is correct
59 Correct 639 ms 91732 KB Output is correct
60 Correct 717 ms 93220 KB Output is correct
61 Correct 700 ms 94160 KB Output is correct
62 Correct 741 ms 101920 KB Output is correct
63 Correct 825 ms 104428 KB Output is correct
64 Correct 836 ms 104780 KB Output is correct
65 Execution timed out 2100 ms 333756 KB Time limit exceeded
66 Halted 0 ms 0 KB -