oj.uz

Submission #286044

# Submission time Handle Problem Language Result Execution time Memory
286044 2020-08-30T02:14:38 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, par;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(), mi = new ArrayList<ArrayList<Integer>>();
	static ArrayList<Integer> mPis = new ArrayList<Integer>(), twos = new 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;
			}
			if (path[i] > maxP){
				maxP = path[i];
				mPis = new ArrayList<Integer>();
				mPis.add(i);
			} else if (path[i] == maxP){
				mPis.add(i);
			}
		} else if (mag[i] == 2){
			twos.add(i);
		}
	}
	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 a : mPis){
				dfs2(a, a+1);
			}
			boolean twok = false;
			for (int i : twos){
				HashSet<Integer> hs = new HashSet<Integer>();
				for (int a : adj.get(i)){
					if (pn[a] != 0){
						hs.add(pn[a]);
					}
				}
				if (hs.size() >= 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 121 ms 12396 KB Output is correct
2 Correct 107 ms 11532 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12520 KB Output is correct
2 Correct 130 ms 12660 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10308 KB Output is correct
2 Runtime error 3911 ms 262144 KB Execution killed with signal 9

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 78068 KB Output is correct
2 Runtime error 3975 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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