JAPLJ Contest B "Banksia"

問題：http://judge.imoz.jp/?cid=8　の問題のページより

本番．

これしか解けなかった．
勝者＝親，敗者＝子，優勝者＝根，の木の深さを計算．

本番中の思考

• トーナメント表…二分木？
• 勝ち負けの関係性で表す木でいいか
• 答えはルートからの深さかな．
• 時間とメモリが他のコンテストより小さくてきつそう．<-勘違い
• （紙で書いてた想定解が間違ってて時間食う）
• （あとはループ回数や配列の参照でバグってて時間食う）
• Submit
  • あれ？クラス名Mainじゃないとダメか．
• Resubmit
  • Accepted

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		int n = next(), k = next();
		int[] a = new int[n + 1], comps = new int[n + 1];
		for (int i = 1; i <= n; ++i) {
			a[i] = i;
			comps[i - 1] = next();
		}
		for (int m = n; m > 1;) {
			m = m / 2 + (m % 2 == 0 ? 0 : 1);
			for (int i = 0; i < m; ++i) {
				int x = next();
				if (comps[2 * i] == x) {
					a[comps[2 * i + 1]] = a[comps[2 * i]];
				} else {
					a[comps[2 * i]] = a[comps[2 * i + 1]];
				}
				comps[i] = x;
			}
			comps[m] = comps[m - 1];
		}
		int[] s = new int[n + 1];
		int[] d = new int[n + 1];
		for (int i = 1; i <= n; ++i) {
			int v = i, c = 1, p = 0;
			for (; v != a[v]; v = a[v]) {
				if (d[a[v]] != 0) {
					c = d[a[v]] + 1;
					break;
				}
				s[p++] = v;
			}
			s[p++] = v;
			while (p > 0) {
				d[s[--p]] = c++;
			}
		}
		for (int i = 1; i <= n; ++i) {
			if (d[i] <= k) {
				pw.println(i);
			}
		}
		pw.close();
	}

	static int next() {
		int r = 0, s = 1, b = ' ';
		try {
			for (; b == '\n' || b == ' '; b = bis.read())
				;
			if ((s = b == '-' ? -1 : 1) < 0) {
				b = bis.read();
			}
			for (; '0' <= b && b <= '9'; b = bis.read())
				r = r * 10 + b - '0';
		} catch (Exception e) {
		}
		return s * r;
	}

	static java.io.BufferedInputStream bis = new BufferedInputStream(System.in);
	static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
}