Submission #485908


Source Code Expand

Copy
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.NoSuchElementException;

public class Main implements Runnable {

	public static void main(String[] args) {
		new Thread(null,new Main(),"",16L*1024*1024).start();
	}

	@SuppressWarnings("unchecked")
	public void run() {
		IO io = new IO();
		int n = io.nextInt();
		ArrayList<Integer>[] graph = new ArrayList[n];
		for(int i=0;i<n;i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for(int i=0;i<n-1;i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			graph[a].add(b);
			graph[b].add(a);
		}
		HashMap<Integer,Integer>[] data = new HashMap[n];
		for(int i=0;i<n;i++) {
			data[i] = new HashMap<Integer,Integer>();
		}
		int q = io.nextInt();
		int[] k = new int[q];
		for(int i=0;i<q;i++) {
			int m = io.nextInt();
			k[i] = io.nextInt();
			for(int j=0;j<m;j++) {
				int v = io.nextInt() - 1;
				data[v].put(i, 1);
			}
		}
		int[] ans = new int[q];
		dfs(0,-1,0,graph,data,k,ans);
		for(int i=0;i<q;i++) {
			io.println(ans[i]);
		}
		io.flush();
	}

	//stack overflow しそう
	public static HashMap<Integer,Integer> dfs(int v,int p,int level,ArrayList<Integer>[] graph, HashMap<Integer,Integer>[] data, int[] k,int[] ans) {
		HashMap<Integer,Integer> a = data[v];
		for(Map.Entry<Integer,Integer> entry: a.entrySet()) {
			int day = entry.getKey();
			if (k[day] == 1) {
				ans[day] = Math.max(ans[day], level);
			}
		}
		for(int u: graph[v]) {
			if (u == p) {
				continue;
			}
			HashMap<Integer,Integer> b = dfs(u,v,level+1,graph,data,k,ans);
			if (a.size() < b.size()) {
				HashMap<Integer,Integer> temp = a;
				a = b;
				b = temp;
			}
			for(Map.Entry<Integer,Integer> entry: b.entrySet()) {
				int day = entry.getKey();
				Integer s1 = a.get(day);
				int s2 = (s1 == null ? 0 : s1) + entry.getValue();
				if (s2 >= k[day]) {
					ans[day] = Math.max(ans[day], level);
				}
				a.put(day, s2);
			}
		}
//		System.out.println(v + "," + level + "," + a);
		return a;
	}

}
class IO extends PrintWriter {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public IO() { this(System.in);}
	public IO(InputStream source) { super(System.out); this.in = source;}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public char[] nextCharArray(int len) {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		char[] s = new char[len];
		int i = 0;
		int b = readByte();
		while(isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}
	public String nextLine() {
		if (!hasNextLine()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(!isNewLine(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public char nextChar() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		return (char) readByte();
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
	public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
	public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
	public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
	public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
	public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
	public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User piroz95
Language Java8 (OpenJDK 1.8.0)
Score 20
Code Size 5821 Byte
Status
Exec Time 2072 ms
Memory 143144 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 20 / 20 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt
Subtask2 0 / 110 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt
Case Name Status Exec Time Memory
sample_01.txt 682 ms 27444 KB
sample_02.txt 387 ms 27308 KB
sample_03.txt 405 ms 27128 KB
subtask_01_01.txt 392 ms 27264 KB
subtask_01_02.txt 391 ms 27312 KB
subtask_01_03.txt 380 ms 27308 KB
subtask_01_04.txt 413 ms 27756 KB
subtask_01_05.txt 530 ms 35428 KB
subtask_01_06.txt 381 ms 27128 KB
subtask_01_07.txt 412 ms 28064 KB
subtask_01_08.txt 516 ms 33604 KB
subtask_01_09.txt 394 ms 27308 KB
subtask_01_10.txt 407 ms 27608 KB
subtask_01_11.txt 508 ms 33032 KB
subtask_01_12.txt 390 ms 27308 KB
subtask_01_13.txt 399 ms 27568 KB
subtask_01_14.txt 527 ms 33576 KB
subtask_01_15.txt 393 ms 27192 KB
subtask_01_16.txt 420 ms 28188 KB
subtask_01_17.txt 519 ms 34232 KB
subtask_01_18.txt 385 ms 27288 KB
subtask_01_19.txt 403 ms 27660 KB
subtask_01_20.txt 505 ms 32540 KB
subtask_01_21.txt 392 ms 27288 KB
subtask_01_22.txt 395 ms 27684 KB
subtask_01_23.txt 519 ms 33880 KB
subtask_01_24.txt 386 ms 27296 KB
subtask_01_25.txt 397 ms 27664 KB
subtask_01_26.txt 496 ms 32596 KB
subtask_02_01.txt 880 ms 75488 KB
subtask_02_02.txt 953 ms 83404 KB
subtask_02_03.txt 1340 ms 113612 KB
subtask_02_04.txt 898 ms 84308 KB
subtask_02_05.txt 905 ms 76592 KB
subtask_02_06.txt 1171 ms 90868 KB
subtask_02_07.txt 949 ms 100436 KB
subtask_02_08.txt 958 ms 98952 KB
subtask_02_09.txt 1209 ms 100304 KB
subtask_02_10.txt 884 ms 79736 KB
subtask_02_11.txt 890 ms 83332 KB
subtask_02_12.txt 1061 ms 82468 KB
subtask_02_13.txt 960 ms 79068 KB
subtask_02_14.txt 990 ms 78372 KB
subtask_02_15.txt 1205 ms 89760 KB
subtask_02_16.txt 861 ms 82284 KB
subtask_02_17.txt 841 ms 86928 KB
subtask_02_18.txt 858 ms 80632 KB
subtask_02_19.txt 929 ms 77824 KB
subtask_02_20.txt 961 ms 77564 KB
subtask_02_21.txt 1209 ms 91084 KB
subtask_02_22.txt 2044 ms 120968 KB
subtask_02_23.txt 903 ms 88260 KB
subtask_02_24.txt 2072 ms 117136 KB
subtask_02_25.txt 1965 ms 143144 KB
subtask_02_26.txt 848 ms 82092 KB