oj.uz

Submission #255335

# Submission time Handle Problem Language Result Execution time Memory
255335 2020-07-31T17:39:36 Z model_code Firefighting (NOI20_firefighting) Java 11
100 / 100
 2104 ms 123500 KB 
import java.io.DataInputStream;
import java.io.IOException;
import java.util.*;
import java.io.*;

public class Firefighting {
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return ret;
        }
        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }
    }
    
    public static class DirectedEdge{
        int target;
        int len;
        public DirectedEdge(int target, int len){
            this.target=target;
            this.len=len;
        }
    }
    public static class Result{
        boolean type;
        long val;
        public Result(boolean type, long val){
            this.type=type;
            this.val=val;
        }
    }
    
    public static ArrayList<DirectedEdge>[] adjlist;
    public static ArrayList<Integer> ans;
    public static long K;
    
    public static Result dfs(int index, int prev, long dist){
        long max_overflow = Long.MIN_VALUE;
        long max_underflow = 0;
        for(DirectedEdge e : adjlist[index]){
            if(e.target != prev){
                Result res = dfs(e.target, index, e.len);
                if(res.type){
                    if(max_overflow < res.val) max_overflow = res.val;
                }
                else {
                    if(max_underflow < res.val) max_underflow = res.val;
                }
            }
        }
        Result ret;
        if(max_overflow >= max_underflow) {
            ret = new Result(true, max_overflow-dist);
        }
        else {
            ret = new Result(false, max_underflow+dist);
        }
        if(!ret.type && ret.val > K){
            ans.add(index);
            ret.type = true;
            ret.val = K-dist;
        }
        if(ret.type && ret.val < 0){
            ret.type = false;
            ret.val = 0;
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
        int N = reader.nextInt();
        K = reader.nextLong();
        adjlist = (ArrayList<DirectedEdge>[]) new ArrayList[N];
        ans = new ArrayList<Integer>();
        for(int i=0;i<N;++i){
            adjlist[i] = new ArrayList<DirectedEdge>();
        }
        for(int i=1;i<N;++i){
            int A = reader.nextInt();
            int B = reader.nextInt();
            int W = reader.nextInt();
            --A;--B;
            adjlist[A].add(new DirectedEdge(B,W));
            adjlist[B].add(new DirectedEdge(A,W));
        }
        dfs(0, -1, Long.MAX_VALUE >> 2);
        out.println(ans.size());
        for(int x : ans){
            out.print(x+1);
            out.print(' ');
        }
        out.flush();
    }
}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 107536 KB Output is correct
2 Correct 1164 ms 114292 KB Output is correct
3 Correct 707 ms 67968 KB Output is correct
4 Correct 1079 ms 107156 KB Output is correct
5 Correct 72 ms 10232 KB Output is correct
6 Correct 70 ms 10352 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 10212 KB Output is correct
2 Correct 76 ms 10180 KB Output is correct
3 Correct 70 ms 10348 KB Output is correct
4 Correct 73 ms 10180 KB Output is correct
5 Correct 76 ms 10232 KB Output is correct
6 Correct 76 ms 10216 KB Output is correct
7 Correct 73 ms 10216 KB Output is correct
8 Correct 75 ms 10232 KB Output is correct
9 Correct 92 ms 10224 KB Output is correct
10 Correct 73 ms 10232 KB Output is correct
11 Correct 72 ms 10212 KB Output is correct
12 Correct 79 ms 10104 KB Output is correct
13 Correct 73 ms 10104 KB Output is correct
14 Correct 72 ms 10232 KB Output is correct
15 Correct 73 ms 10360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10304 KB Output is correct
2 Correct 75 ms 10340 KB Output is correct
3 Correct 92 ms 10236 KB Output is correct
4 Correct 79 ms 10360 KB Output is correct
5 Correct 74 ms 10232 KB Output is correct
6 Correct 74 ms 10104 KB Output is correct
7 Correct 80 ms 10228 KB Output is correct
8 Correct 79 ms 10360 KB Output is correct
9 Correct 74 ms 10232 KB Output is correct
10 Correct 70 ms 10232 KB Output is correct
11 Correct 74 ms 10228 KB Output is correct
12 Correct 71 ms 10232 KB Output is correct
13 Correct 77 ms 10232 KB Output is correct
14 Correct 70 ms 10232 KB Output is correct
15 Correct 72 ms 10216 KB Output is correct
16 Correct 71 ms 10236 KB Output is correct
17 Correct 73 ms 10236 KB Output is correct
18 Correct 81 ms 10244 KB Output is correct
19 Correct 79 ms 10352 KB Output is correct
20 Correct 80 ms 10232 KB Output is correct
21 Correct 73 ms 10232 KB Output is correct
22 Correct 79 ms 10228 KB Output is correct
23 Correct 74 ms 10344 KB Output is correct
24 Correct 81 ms 10232 KB Output is correct
25 Correct 74 ms 10232 KB Output is correct
26 Correct 75 ms 10232 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 109292 KB Output is correct
2 Correct 746 ms 72992 KB Output is correct
3 Correct 770 ms 75248 KB Output is correct
4 Correct 674 ms 69844 KB Output is correct
5 Correct 80 ms 10256 KB Output is correct
6 Correct 79 ms 10340 KB Output is correct
7 Correct 1284 ms 98816 KB Output is correct
8 Correct 1173 ms 97312 KB Output is correct
9 Correct 1200 ms 99876 KB Output is correct
10 Correct 1156 ms 99760 KB Output is correct
11 Correct 1131 ms 110452 KB Output is correct
12 Correct 877 ms 80680 KB Output is correct
13 Correct 793 ms 68724 KB Output is correct
14 Correct 797 ms 76944 KB Output is correct
15 Correct 941 ms 90640 KB Output is correct
16 Correct 1205 ms 92548 KB Output is correct
17 Correct 887 ms 79416 KB Output is correct
18 Correct 882 ms 79772 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11840 KB Output is correct
2 Correct 98 ms 10928 KB Output is correct
3 Correct 89 ms 10512 KB Output is correct
4 Correct 90 ms 10680 KB Output is correct
5 Correct 136 ms 12228 KB Output is correct
6 Correct 129 ms 12284 KB Output is correct
7 Correct 141 ms 12624 KB Output is correct
8 Correct 131 ms 12576 KB Output is correct
9 Correct 123 ms 11924 KB Output is correct
10 Correct 129 ms 11836 KB Output is correct
11 Correct 131 ms 12412 KB Output is correct
12 Correct 119 ms 11540 KB Output is correct
13 Correct 137 ms 12212 KB Output is correct
14 Correct 122 ms 11968 KB Output is correct
15 Correct 128 ms 11948 KB Output is correct
16 Correct 97 ms 10952 KB Output is correct
17 Correct 100 ms 10680 KB Output is correct
18 Correct 103 ms 11192 KB Output is correct
19 Correct 92 ms 10944 KB Output is correct
20 Correct 95 ms 10952 KB Output is correct
21 Correct 94 ms 11908 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 81396 KB Output is correct
2 Correct 733 ms 78888 KB Output is correct
3 Correct 661 ms 78544 KB Output is correct
4 Correct 346 ms 34636 KB Output is correct
5 Correct 1422 ms 107028 KB Output is correct
6 Correct 1245 ms 108948 KB Output is correct
7 Correct 2008 ms 112704 KB Output is correct
8 Correct 2104 ms 105332 KB Output is correct
9 Correct 1291 ms 91260 KB Output is correct
10 Correct 1006 ms 91560 KB Output is correct
11 Correct 1138 ms 123500 KB Output is correct
12 Correct 627 ms 74088 KB Output is correct
13 Correct 1403 ms 110460 KB Output is correct
14 Correct 1147 ms 91104 KB Output is correct
15 Correct 827 ms 80624 KB Output is correct
16 Correct 630 ms 79760 KB Output is correct
17 Correct 775 ms 79372 KB Output is correct
18 Correct 807 ms 79424 KB Output is correct
19 Correct 707 ms 74436 KB Output is correct
20 Correct 257 ms 31876 KB Output is correct
21 Correct 755 ms 78992 KB Output is correct