oj.uz

Submission #286046

# Submission time Handle Problem Language Result Execution time Memory
286046 2020-08-30T02:27:19 Z FlashGamezzz Mag (COCI16_mag) Java 11
24 / 120
 4000 ms 262152 KB 
import java.io.*;
import java.util.*;

public class mag {
	static int n, minM = Integer.MAX_VALUE, maxP = 0;
	static int[] mag, pd, path, pn;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(), mi = new ArrayList<ArrayList<Integer>>();
	static void dfs(int i, int p) {
		minM = Integer.min(minM, mag[i]);
		for (int a : adj.get(i)) {
			if (a != p) {
				dfs(a, i);
			}
		}
		if (mag[i] == 1) {
			pd[i] = 1;
			for (int a : adj.get(i)) {
				if (a != p && mag[a] == 1) {
					if (pd[a]+1 > pd[i]) {
						pd[i] = pd[a]+1;
						ArrayList<Integer> t= new ArrayList<Integer>();
						t.add(a);
						mi.set(i, t);
					} else if (pd[a]+1 == pd[i]) {
						mi.get(i).add(a);
					}
				}
			}
			ArrayList<Integer> minds = mi.get(i);
			path[i] = pd[i];
			if (minds.size() == 1){
				int mind = minds.get(0);
				ArrayList<Integer> t = new ArrayList<Integer>();
				for (int a : adj.get(i)){
					if (a != p && mag[a] == 1 && a != mind ) {
						if (pd[i]+pd[a] > path[i]){
							path[i] = pd[i]+pd[a];
							t = new ArrayList<Integer>();
							t.add(a);
						} else if (pd[i]+pd[a] == path[i]){
							t.add(a);
						}
					}
				}
				minds.addAll(t);
			} else if (minds.size() > 1){
				path[i] = 2*pd[i]-1;
			}
			maxP = Integer.max(path[i], maxP);
		}
	}
	static void dfs2(int i, int v){
		pn[i] = v;
		for (int a : mi.get(i)) {
			dfs2(a, v);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		n = Integer.parseInt(br.readLine());
		mag = new int[n];
		for (int i = 0; i < n; i++) {
			mi.add(new ArrayList<Integer>());
			adj.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < n-1; i++) {
			String[] line = br.readLine().split(" ");
			int a = Integer.parseInt(line[0])-1, b = Integer.parseInt(line[1])-1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
		for (int i = 0; i < n; i++) {
			mag[i] = Integer.parseInt(br.readLine());
		}
		pd = new int[n];
		path = new int[n];
		dfs(0, -1);
		if (minM == 1){
			pn = new int[n];
			for (int i = 0; i < n; i++){
				if (path[i] == maxP){
					dfs2(i, i+1);
				}
			}
			boolean twok = false;
			for (int i = 0; i < n; i++){
				if (mag[i] == 2){
					int count = 0;
					for (int a : adj.get(i)){
						if (pn[a] != 0){
							count++;
							if (count >= 2){
								twok = true;
								break;
							}
						}
					}
				}
			}
			if (twok){
				pw.println("2/"+(2*maxP+1));
			} else {
				pw.println("1/"+maxP);
			}
		} else {
			pw.println(minM+"/1");
		}
		pw.close();
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 12136 KB Output is correct
2 Correct 118 ms 11376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12364 KB Output is correct
2 Correct 143 ms 13468 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4570 ms 191176 KB Time limit exceeded

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10404 KB Output is correct
2 Runtime error 3869 ms 262152 KB Execution killed with signal 9

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3914 ms 262144 KB Execution killed with signal 9

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3947 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 75960 KB Output is correct
2 Execution timed out 4040 ms 241156 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3805 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

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