Submission #286044

#	Time	Username	Problem	Language	Result	Execution time	Memory
286044		FlashGamezzz	Mag (COCI16_mag)	Java	24 / 120	4148 ms	262152 KiB

mag

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12