oj.uz

Submission #382632

# Submission time Handle Problem Language Result Execution time Memory
382632 2021-03-27T23:30:11 Z vijay Triumphal arch (POI13_luk) Java 11
60 / 100
 2000 ms 65768 KB 
import java.io.*;
import java.util.*;

public class luk {
    static int N;
    static ArrayList<Integer>[] adj;
    public static void main(String[] args) throws IOException, FileNotFoundException {
        Scanner in = new Scanner(System.in);
        // Scanner in = new Scanner(new File("luk.in"));
        // PrintWriter out = new PrintWriter("luk.out");

        N = in.nextInt();
        adj = new ArrayList[N];

        for(int i = 0; i < N; i++){
            adj[i] = new ArrayList<>(); 
        }

        for(int i = 0; i < N - 1; i++){
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            adj[a].add(b);
            adj[b].add(a);
        }

        int a = 1;
        int b = N;
        while(a != b){
            int mid = (a + b)/2;
            if(recurse(0, -1, mid) <= 0){
                b = mid;
            } else {
                a = mid + 1;
            }
        }

        System.out.println(a);
    }

    static int recurse(int position, int prev, int crew){
        int j = 0;
        for(int ap: adj[position]){
            if(ap != prev){
                j += recurse(ap, position, crew) + 1;
            }
        }
        return Math.max(0, j - crew);
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 10344 KB Output is correct
2 Correct 119 ms 10348 KB Output is correct
3 Correct 121 ms 10436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 10476 KB Output is correct
2 Correct 122 ms 10344 KB Output is correct
3 Correct 124 ms 10604 KB Output is correct
4 Correct 121 ms 10220 KB Output is correct
5 Incorrect 122 ms 10368 KB Output isn't correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 11228 KB Output is correct
2 Correct 155 ms 11476 KB Output is correct
3 Correct 151 ms 11352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 13864 KB Output is correct
2 Correct 299 ms 13580 KB Output is correct
3 Correct 304 ms 13452 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 19416 KB Output is correct
2 Correct 682 ms 19712 KB Output is correct
3 Correct 678 ms 19744 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 21900 KB Output is correct
2 Correct 813 ms 23056 KB Output is correct
3 Correct 757 ms 22504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1529 ms 34752 KB Output is correct
2 Correct 1576 ms 37232 KB Output is correct
3 Correct 1149 ms 35888 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 51684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 65768 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 65672 KB Time limit exceeded
2 Halted 0 ms 0 KB -