Submission #1094265


Source Code Expand

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int[] a = na(n);
		int[] from = new int[n - 1];
		int[] to = new int[n - 1];
		for (int i = 0; i < n - 1; i++) {
			from[i] = ni() - 1;
			to[i] = ni() - 1;
		}
		int[][] g = packU(n, from, to);
		
		for(int i = 0;i < n;i++){
			if(ok(i, g, Arrays.copyOf(a, n))){
				out.print((i+1) + " ");
			}
		}
		out.println();
	}
	
	static boolean ok(int start, int[][] g, int[] a)
	{
		if(a[start] == 0)return false;
		for(int e : g[start]){
			if(a[e] < a[start]){
				a[start]--;
				boolean res = ok(e, g, a);
				a[start]++;
				if(!res)return true;
			}
		}
		return false;
	}

	public static int[][] parents3(int[][] g, int root) {
		int n = g.length;
		int[] par = new int[n];
		Arrays.fill(par, -1);

		int[] depth = new int[n];
		depth[0] = 0;

		int[] q = new int[n];
		q[0] = root;
		for (int p = 0, r = 1; p < r; p++) {
			int cur = q[p];
			for (int nex : g[cur]) {
				if (par[cur] != nex) {
					q[r++] = nex;
					par[nex] = cur;
					depth[nex] = depth[cur] + 1;
				}
			}
		}
		return new int[][] { par, q, depth };
	}

	static int[][] packU(int n, int[] from, int[] to) {
		int[][] g = new int[n][];
		int[] p = new int[n];
		for (int f : from)
			p[f]++;
		for (int t : to)
			p[t]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]];
		for (int i = 0; i < from.length; i++) {
			g[from[i]][--p[from[i]]] = to[i];
			g[to[i]][--p[to[i]]] = from[i];
		}
		return g;
	}

	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Submission Time
Task F - Tree Game
User uwi
Language Java8 (OpenJDK 1.8.0)
Score 1600
Code Size 4896 Byte
Status AC
Exec Time 141 ms
Memory 24784 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 3
AC × 53
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in5.txt, in50.txt, in6.txt, in7.txt, in8.txt, in9.txt
Case Name Status Exec Time Memory
in1.txt AC 140 ms 24656 KB
in10.txt AC 141 ms 24524 KB
in11.txt AC 132 ms 24656 KB
in12.txt AC 116 ms 11600 KB
in13.txt AC 108 ms 12240 KB
in14.txt AC 141 ms 24656 KB
in15.txt AC 140 ms 24528 KB
in16.txt AC 141 ms 24660 KB
in17.txt AC 133 ms 24524 KB
in18.txt AC 131 ms 24660 KB
in19.txt AC 138 ms 24524 KB
in2.txt AC 140 ms 24528 KB
in20.txt AC 139 ms 24656 KB
in21.txt AC 138 ms 24660 KB
in22.txt AC 140 ms 24780 KB
in23.txt AC 140 ms 24532 KB
in24.txt AC 137 ms 24660 KB
in25.txt AC 141 ms 24656 KB
in26.txt AC 140 ms 24656 KB
in27.txt AC 141 ms 24652 KB
in28.txt AC 130 ms 24528 KB
in29.txt AC 140 ms 24528 KB
in3.txt AC 140 ms 24660 KB
in30.txt AC 133 ms 24784 KB
in31.txt AC 134 ms 24528 KB
in32.txt AC 125 ms 24400 KB
in33.txt AC 124 ms 24532 KB
in34.txt AC 135 ms 24660 KB
in35.txt AC 124 ms 24652 KB
in36.txt AC 95 ms 8144 KB
in37.txt AC 96 ms 8016 KB
in38.txt AC 94 ms 8144 KB
in39.txt AC 95 ms 8016 KB
in4.txt AC 140 ms 24528 KB
in40.txt AC 130 ms 24660 KB
in41.txt AC 125 ms 24528 KB
in42.txt AC 127 ms 24652 KB
in43.txt AC 126 ms 24660 KB
in44.txt AC 127 ms 24784 KB
in45.txt AC 124 ms 24404 KB
in46.txt AC 122 ms 24528 KB
in47.txt AC 126 ms 24532 KB
in48.txt AC 128 ms 24528 KB
in49.txt AC 139 ms 24656 KB
in5.txt AC 121 ms 23636 KB
in50.txt AC 139 ms 24656 KB
in6.txt AC 137 ms 24656 KB
in7.txt AC 138 ms 24656 KB
in8.txt AC 129 ms 24660 KB
in9.txt AC 138 ms 24532 KB
sample1.txt AC 92 ms 8144 KB
sample2.txt AC 93 ms 8144 KB
sample3.txt AC 93 ms 8140 KB