#538122 (Java21) No.1188 レベルX門松列

提出ソース
結果

問題	No.1188 レベルX門松列
ユーザー	CaliPota
提出日時	2020-08-22 16:29:53
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,012 ms / 2,000 ms
コード長	20,075 bytes
コンパイル時間	5,371 ms
コンパイル使用メモリ	91,424 KB
実行使用メモリ	58,468 KB
最終ジャッジ日時	2024-10-15 10:28:55
合計ジャッジ時間	16,412 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	608 ms 57,888 KB
testcase_01	AC	776 ms 56,652 KB
testcase_02	AC	708 ms 57,376 KB
testcase_03	AC	1,012 ms 58,468 KB
testcase_04	AC	796 ms 58,100 KB
testcase_05	AC	48 ms 37,040 KB
testcase_06	AC	549 ms 57,412 KB
testcase_07	AC	654 ms 57,992 KB
testcase_08	AC	866 ms 57,840 KB
testcase_09	AC	48 ms 36,864 KB
testcase_10	AC	47 ms 36,508 KB
testcase_11	AC	135 ms 43,136 KB
testcase_12	AC	150 ms 44,252 KB
testcase_13	AC	151 ms 44,072 KB
testcase_14	AC	687 ms 55,296 KB
testcase_15	AC	922 ms 57,068 KB
testcase_16	AC	68 ms 37,644 KB
testcase_17	AC	854 ms 54,196 KB
testcase_18	AC	48 ms 37,004 KB
testcase_19	AC	700 ms 57,312 KB
testcase_20	AC	48 ms 36,512 KB
testcase_21	AC	50 ms 36,688 KB
testcase_22	AC	48 ms 36,560 KB
testcase_23	AC	48 ms 36,804 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {

	//私が好きなアルゴリズム : 累積和・UF木
	//PriorityQueueは拡張for文で出すとsortされてない順番で出てくるよ
	//longのbit演算は1L<<posに注意
	//long long
	//JOIはMLEが厳しい。shortというものがあるよ。あと、ArrayListはオートボクシングが遅いから、自作listが早いよ

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nexI();
		
		if(n<=2) {
			System.out.println(0);
			return;
		}
		
		long[] as = new long[n];
		sc.al(as);
		
		int left = 0, right = n;
		
		whle:
		while((right-left)>1) {
			int mid = (right+left)/2;

			//まず山形門松
			
			//1-左からLIS	
			long[] dpl = new long[n];
			fill(dpl, INFL);
			long[] least = new long[n];
			for(int i=0; i<n; i++) {
				int ad = biSearchMax(dpl, as[i]);
				dpl[ad+1] = as[i];
				least[i] = dpl[mid-1];
			}
			
			//2-右からLIS
			long[] dpr = new long[n];
			fill(dpr, INFL);
			long[] reast = new long[n];
			for(int i=0; i<n; i++) {
				int ad = biSearchMax(dpr, as[n-i-1]);
				dpr[ad+1] = as[n-i-1];
				reast[n-i-1] = dpr[mid-1];
			}
			
			for(int i=1; i<(n-1); i++) {
				if((least[i-1]<as[i])&&(reast[i+1]<as[i])) {
					left = mid;
					continue whle;
				}
			}
			//次は谷形
			
			//1-左からLDS
			fill(dpl, -INFL);
			for(int i=0; i<n; i++) {
				int ad = biSearchmin(dpl, as[i]);
				dpl[ad+1] = as[i];
				least[i] = dpl[mid-1];
			}
			
			//2-右からLIS
			fill(dpr, -INFL);
			for(int i=0; i<n; i++) {
				int ad = biSearchmin(dpr, as[n-i-1]);
				dpr[ad+1] = as[n-i-1];
				reast[n-i-1] = dpr[mid-1];
			}
			
			for(int i=1; i<(n-1); i++) {
				if((least[i-1]>as[i])&&(reast[i+1]>as[i])) {
					left = mid;
					continue whle;
				}
			}
			right = mid;
		}
		
		out.println(left);
		
		out.flush();
		return;
	}
	private static int INF = 100000000;
	private static long INFL = 100000000000000000L;
	private static long e97 = 1000000007L;
	private static long e99 = 998244353L;

	private static void assertion(boolean b) {
		if(!b) throw new AssertionError();
	}

	private static int pow2(int in) {
		return in*in;
	}
	private static long pow2(long in) {
		return in*in;
	}
	private static double pow2(double in) {
		return in*in;
	}

	private static int getDigit2(long num) {
		long cf = 1;
		int d = 0;
		while(num > cf) {
			d ++;
			cf = (1L<<d);
		}
		return d; //numは2^d以下
	}
	private static int getDigit10(long num) {
		long cf = 1L;
		int d = 0;
		while(num >= cf) {
			d ++;
			cf *= 10L;
		}
		return d; //numはd桁の数で、10^dより小さい

	}

	private static int divceil(int nume, int deno) {
		return (nume+deno-1)/deno;
	}
	private static long divceil(long nume, long deno) {
		return (nume+deno-1L)/deno;
	}

	private static boolean isINF(long in) {
		if((in*20L)>INF) return true;
		else return false;
	}
	private static boolean isINFL(long in) {
		if((in*10L)>INFL) return true;
		else return false;
	}

	public static int biSearchMax(long[] dt, long target) {
		int left=-1, right=dt.length, mid=-1;
		while((right-left)>1) {
			mid = (right+left)/2;
			if(dt[mid] < target) left=mid;
			else right=mid;
		}
		return left;	//target未満の最大のaddress
	}
	public static int biSearchmin(long[] dt, long target) {	//単調減少文字列
		int left=-1, right=dt.length, mid=-1;
		while((right-left)>1) {
			mid = (right+left)/2;
			if(dt[mid] > target) left=mid;
			else right=mid;
		}
		return left;	//targetより大きい最大のaddress
	}
	public static int biSearchMaxAL(ArrayList<Long> dt, long target) {
		int left=-1, right=dt.size(), mid=-1;
		while((right-left)>1) {
			mid = (right+left)/2;
			if(dt.get(mid) <= target) left=mid;
			else right=mid;
		}
		return left;//target以下の最大のaddress
	}

	private static int[] Xdir4 = {1,0,0,-1};
	private static int[] Ydir4 = {0,1,-1,0};
	private static int[] Xdir8 = {1,1,1,0,0,-1,-1,-1};
	private static int[] Ydir8 = {1,0,-1,1,-1,1,0,-1};

	private static boolean is_in_area(int y, int x, int h, int w) {
		if(y < 0) return false;
		if(x < 0) return false;
		if(y >= h) return false;
		if(x >= w) return false;
		return true;
	}

	private static int abs(int a) {
		return (a>=0) ? a: -a;
	}
	private static long abs(long a) {
		return (a>=0) ? a: -a;
	}
	private static double abs(double a) {
		return (a>=0) ? a: -a;
	}

	private static int min(int a, int b) {
		return (a>b) ? b : a;
	}
	private static long min(long a, long b) {
		return (a>b) ? b : a;
	}
	private static double min(double a, double b) {
		return (a>b) ? b : a;
	}

	private static int max(int a, int b) {
		return (a>b) ? a : b;
	}
	private static long max(long a, long b) {
		return (a>b) ? a : b;
	}
	private static double max(double a, double b) {
		return (a>b) ? a : b;
	}

	private static int minN(int... ins) {
		int min = ins[0];
		for(int i=1; i<ins.length; i++) {
			if(ins[i] < min) min = ins[i];
		}
		return min;
	}
	private static long minN(long... ins) {
		long min = ins[0];
		for(int i=1; i<ins.length; i++) {
			if(ins[i] < min) min = ins[i];
		}
		return min;
	}
	private static int maxN(int... ins) {
		int max = ins[0];
		for(int i=1; i<ins.length; i++) {
			if(ins[i] > max) max = ins[i];
		}
		return max;
	}
	private static long maxN(long... ins) {
		long max = ins[0];
		for(int i=1; i<ins.length; i++) {
			if(ins[i] > max) max = ins[i];
		}
		return max;
	}

	private static int minExAd(int[] dt, int ad) {
		int min = Integer.MAX_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((i!=ad) && (dt[i]<min)) min = dt[i];
		}
		return min;
	}
	private static long minExAd(long[] dt, int ad) {
		long min = Long.MAX_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((i!=ad) && (dt[i]<min)) min = dt[i];
		}
		return min;
	}
	private static int minExVal(int[] dt, int ex_val) {
		int min = Integer.MAX_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((dt[i]!=ex_val) && (dt[i]<min)) min = dt[i];
		}
		return min;
	}
	private static long minExVal(long[] dt, long ex_val) {
		long min = Long.MAX_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((dt[i]!=ex_val) && (dt[i]<min)) min = dt[i];
		}
		return min;
	}
	private static int maxExAd(int[] dt, int ad) {
		int max = Integer.MIN_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((i!=ad) && (dt[i]>max)) max = dt[i];
		}
		return max;
	}
	private static long maxExAd(long[] dt, int ad) {
		long max = Long.MIN_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((i!=ad) && (dt[i]>max)) max = dt[i];
		}
		return max;
	}
	private static int maxExVal(int[] dt, int ex_val) {
		int max = Integer.MIN_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((dt[i]!=ex_val) && (dt[i]>max)) max = dt[i];
		}
		return max;
	}
	private static long maxExVal(long[] dt, long ex_val) {
		long max = Long.MIN_VALUE;
		for(int i=0; i<dt.length; i++) {
			if((dt[i]!=ex_val) && (dt[i]>max)) max = dt[i];
		}
		return max;
	}

	private static int sumA(int[] dt) {
		int sum = 0;
		for(int e: dt) {
			sum += e;
		}
		return sum;
	}
	private static long sumA(long[] dt) {
		long sum = 0L;
		for(long e: dt) {
			sum += e;
		}
		return sum;
	}
	private static long sumA(ArrayList<Long> dt) {
		long sum =0L;
		for(long e: dt) {
			sum += e;
		}
		return sum;
	}

	private static int pow(int n, int k) {
		int ans = 1;
		for(int i=0; i<k; i++) {
			ans *= n;
			assertion(n>=0);
		}
		return ans;
	}
	private static long pow(long n, int k) {
		long ans = 1L;
		for(int i=0; i<k; i++) {
			ans *= n;
			assertion(n>=0L);
		}
		return ans;
	}

	private static double hypod(double a, double b) {
		return Math.sqrt(a*a+b*b);
	}

	private static long factorial(int n) {
		long ans=1L;
		for(long i=n; i>0; i--) {
			ans *= i;
			assertion(ans>=0L);
		}
		return ans;
	}
	private static long facP(int n, long p) {
		long ans=1L;
		for(long i=n; i>0; i--) {
			ans *= i;
			ans %= p;
		}
		return ans;
	}

	private static long lcm(long m, long n) {
		assertion((m>0L) && (n>0L));
		long ans = m/gcd(m,n);
		ans *= n;
		return ans;
	}
	private static long gcd(long m, long n) {
		if(isINFL(-m)) return n;
		assertion((m>=0L) && (n>=0L));
		if(m < n) return gcd(n, m);
		if(n == 0) return m;
		return gcd(n, m % n);
	}

	private static boolean is_prime(long a) {
		if(a==1) return false;
		for(long i=2L; i<=Math.sqrt(a); i++) {
			if(a%i == 0) return false;
		}
		return true;
	}

	private static long modinv(long a, long p) {
		assertion((a>0)&&(p>1)&&(a%p != 0));
		//a|p, >1に注意
		long b = p, u = 1L, v = 0L;
		while (b > 0) {
			long t = a / b;
			long pe = a%b;
			a = b;
			b = pe;
			pe = u-t*v;
			u = v;
			v = pe;
		}
		u %= p;
		if(u < 0L) u += p;
		return u;
	}

	private static long pow10E97(long ob, long soeji, long p) {		//繰り返し二乗法
		if(ob==0) return 0L;
		if(soeji==0) return 1L;
		if(soeji==2) return (ob*ob)%p;

		long cf = 1L;
		int d = 0;
		while(soeji >= cf) {
			d ++;
			cf = (1L<<d);
		}

		long[] ob_pow_2pow = new long[d];
		ob_pow_2pow[0] = ob;
		for(int i=1; i<d; i++) {
			ob_pow_2pow[i] = (ob_pow_2pow[i-1]*ob_pow_2pow[i-1])%p;
		}
		long ans=1L;
		for(long i=(d-1); i>=0L; i--) {
			if(soeji >= (1L<<i)) {
				soeji -= (1L<<i);
				ans = (ans*ob_pow_2pow[(int)i])%p;
			}
 		}
		return ans%p;
	}

	private static int inC2(int n) {
		return ((n*(n-1))/2);
	}
	private static long nC2(long n) {
		return ((n*(n-1L))/2L);
	}

	private static int intflag(int pos) {
		assertion(pos<31);
		return (1<<pos);
	}
	private static long flag(long pos) {
		assertion(pos<63);
		return (1L<<pos);
	}
	private static boolean isFlaged(int bit, int pos) {
		if((bit&(1<<pos)) > 0) return true;
		else return false;
	}
	private static boolean isFlaged(long bit, int pos) {
		if((bit&(1L<<pos)) > 0L) return true;
		else return false;
	}
	private static int ideflag(int bit, int pos) {
		return bit&~(1<<pos);
	}
	private static int countFlaged(int bit) {
		int ans=0;
		for(int i=0; i<31; i++) {
			if((bit&(1<<i)) > 0) ans++;
		}
		return ans;
	}
	private static int countFlaged(long bit) {
		int ans=0;
		for(long i=0; i<63; i++) {
			if((bit&(1L<<i)) > 0) ans++;
		}
		return ans;
	}

	public static int biSearch(int[] dt, int target) {
		int left=0, right=dt.length-1;
		int mid=-1;
		while(left<=right) {
			mid = (right+left)/2;
			if(dt[mid] == target) return mid;
			if(dt[mid] < target) left=mid+1;
			else right=mid-1;
		}
		return -1;
	}

	private static void show2(int bit) {
		for(int i=0; i<getDigit2(bit); i++) {
			if(isFlaged(bit,i)) System.out.print("O");
			else System.out.print(".");
		}
		System.out.println();
	}
	static void show2(boolean[][] dt, int lit_x, int lit_y) {
		for(int j=0; j<dt.length; j++) {
			for(int i=0; i<dt[j].length; i++) {
				if((i==lit_y) && (j==lit_x)) System.out.print("X");
				else if(dt[j][i]) System.out.print("O");
				else System.out.print(".");
			}
			System.out.println();
		}
	}
	static void show2(int[][] dt, String cmnt) {
		for(int i=0; i<dt.length; i++) {
			for(int j=0; j<dt[i].length; j++) {
				System.out.print(dt[i][j]+",");
			}
			System.out.println("<-"+cmnt+":"+i);
		}
	}
	static void show2(long[][] dt, String cmnt) {
		for(int i=0; i<dt.length; i++) {
			for(int j=0; j<dt[i].length; j++) {
				System.out.print(dt[i][j]+",");
			}
			System.out.println("<-"+cmnt+":"+i);
		}
	}
	static void show2(ArrayDeque<Long> dt) {		//上手くいかなかった時用
		long a=0;
		while(dt.size()>0) {
			a=dt.removeFirst();
			System.out.print(a);
		}
		System.out.println("\n");
	}
	static void show2(List dt) {		//上手くいかなかった時用
	 	for(int i=0; i<dt.size(); i++) {
			System.out.print(dt.get(i)+",");
		}
		System.out.println("\n");
	}

	private static void prtlnas(int[] as) {
		PrintWriter out = new PrintWriter(System.out);
		for(int i=0; i<as.length; i++) {
			out.println(as[i]);
		}
		out.flush();
	}
	private static void prtlnas(long[] as) {
		PrintWriter out = new PrintWriter(System.out);
		for(int i=0; i<as.length; i++) {
			out.println(as[i]);
		}
		out.flush();
	}
	private static void prtspas(int[] as) {
		PrintWriter out = new PrintWriter(System.out);
		out.print(as[0]);
		for(int i=1; i<as.length; i++) {
			out.print(" "+as[i]);
		}
		out.println();
		out.flush();
	}
	private static void prtspas(long[] as) {
		PrintWriter out = new PrintWriter(System.out);
		out.print(as[0]);
		for(int i=1; i<as.length; i++) {
			out.print(" "+as[i]);
		}
		out.println();
		out.flush();
	}
	private static void prtspas(ArrayList as) {
		PrintWriter out = new PrintWriter(System.out);
		out.print(as.get(0));
		for(int i=1; i<as.size(); i++) {
			out.print(" "+as.get(i));
		}
		out.println();
		out.flush();
	}

	private static void fill(boolean[] ob, boolean res) {
		for(int i=0; i<ob.length; i++) {
			ob[i] = res;
		}
	}
	private static void fill(int[] ob, int res) {
		for(int i=0; i<ob.length; i++) {
			ob[i] = res;
		}
	}
	private static void fill(long[] ob, long res) {
		for(int i=0; i<ob.length; i++) {
			ob[i] = res;
		}
	}
	private static void fill(char[] ob, char res) {
		for(int i=0; i<ob.length; i++) {
			ob[i] = res;
		}
	}
	private static void fill(double[] ob, double res) {
		for(int i=0; i<ob.length; i++) {
			ob[i] = res;
		}
	}
	private static void fill(boolean[][] ob,boolean res) {
		for(int i=0;i<ob.length; i++) {
			for(int j=0; j<ob[0].length; j++) {
				ob[i][j] = res;
			}
		}
	}
	private static void fill(int[][] ob, int res) {
		for(int i=0; i<ob.length; i++) {
			for(int j=0; j<ob[0].length; j++) {
				ob[i][j] = res;
			}
		}
	}
	private static void fill(long[][] ob, long res) {
		for(int i=0; i<ob.length; i++) {
			for(int j=0; j<ob[0].length; j++) {
				ob[i][j] = res;
			}
		}
	}
	private static void fill(char[][] ob, char res) {
		for(int i=0; i<ob.length; i++) {
			for(int j=0; j<ob[0].length; j++) {
				ob[i][j] = res;
			}
		}
	}
	private static void fill(double[][] ob, double res) {
		for(int i=0; i<ob.length; i++) {
			for(int j=0; j<ob[0].length; j++) {
				ob[i][j] = res;
			}
		}
	}
	private static void fill(int[][][] ob,int res) {
		for(int i=0;i<ob.length;i++) {
			for(int j=0;j<ob[0].length;j++) {
				for(int k=0;k<ob[0][0].length;k++) {
					ob[i][j][k]=res;
				}
			}
		}
	}
	private static void fill(long[][][] ob,long res) {
		for(int i=0;i<ob.length;i++) {
			for(int j=0;j<ob[0].length;j++) {
				for(int k=0;k<ob[0][0].length;k++) {
					ob[i][j][k]=res;
				}
			}
		}
	}
	static class FastScanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		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);
		}
		public boolean hasNext() {
			while(hasNextByte() && !isPrintableChar(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 long nexL() {
			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) || b == ':') {
					return minus ? -n : n;
				}else{
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}
		public int nexI() {
			long nl = nexL();
			if(nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
			return (int) nl;
		}
		public double nexD() { return Double.parseDouble(next());}
		public void al(long[] array) {
		 	for(int i=0; i<array.length; i++) {
		 		array[i] = nexL();
		 	}
		 	return;
		}
		public void ai(int[] array) {
		 	for(int i=0; i<array.length; i++) {
		 		array[i] = nexI();
		 	}
		 	return;
		}
		public void aimin1(int[] array) {
		 	for(int i=0; i<array.length; i++) {
		 		array[i] = nexI()-1;
		 	}
		 	return;
		}
		public void aD(double[] array) {
		 	for(int i=0; i<array.length; i++) {
		 		array[i] = nexD();
		 	}
		 	return;
		}
		public void ai2(int[] as, int[] bs) {
		 	for(int i=0; i<as.length; i++) {
				as[i] = nexI();
				bs[i] = nexI();
		 	}
		 	return;
		}
		public void al2(long[] as, long[] bs) {
		 	for(int i=0; i<as.length; i++) {
				as[i] = nexL();
				bs[i] = nexL();
		 	}
		 	return;
		}
		public void ai3(int[] as, int[] bs, int[] cs) {
		 	for(int i=0; i<as.length; i++) {
				as[i] = nexI();
				bs[i] = nexI();
				cs[i] = nexI();
		 	}
		 	return;
		}
		public void ad2i(int[][] as) {
			for(int i=0; i<as.length; i++) {
				for(int j=0; j<as[0].length; j++) {
					as[i][j] = nexI();
				}
			}
			return;
		}
		public void ain(int[]... as) {
			for(int i=0; i<as[0].length; i++) {
				for(int j=0; j<as.length; j++) {
					as[j][i] = nexI();
				}
			}
			return;
		}
		public void aln(long[]... as) {
			for(int i=0; i<as[0].length; i++) {
				for(int j=0; j<as.length; j++) {
					as[j][i] = nexL();
				}
			}
			return;
		}
	}

	static class Graph0n {
		private ArrayList<Node0n> dt = new ArrayList<>();
		Graph0n(int sz) {
			for(int i = 0; i < sz; i++) {
				Node0n node1 = new Node0n();
				dt.add(node1);
			}
		}
		public void add(int vn, int val) {
			dt.get(vn).add(val);
		}
		public void add2(int vn, int val) {
			dt.get(vn).add(val);
			dt.get(val).add(vn);
		}
		public int get(int vn, int index) {
			return dt.get(vn).get(index);
		}
		public ArrayList<Integer> get(int vn) {
			return dt.get(vn).getAll();
		}
		public int size() {
			return dt.size();
		}
		public int sizeOf(int vn) {
			return dt.get(vn).size();
		}
		public void clear() {
			for(int i = 0; i < dt.size(); i++) {
				dt.get(i).clear();
			}
		}
		public void clear(int i) {
			dt.get(i).clear();
		}
		public static Graph0n make_tree(int vn, FastScanner sc) {
			Graph0n tree = new Graph0n(vn);
			for(int i = 1; i < vn; i++) {
				int s1 = sc.nexI() - 1;
				int g1 = sc.nexI() - 1;
				tree.add2(s1, g1);
			}
			return tree;
		}
		private void add_Vertex(Node0n vnew) {
			dt.add(vnew);
		}
	}

	static class Node0n { // 重みなし無向・有向グラフの頂点
		private ArrayList<Integer> next_vs = new ArrayList<>();
		public void add(int val) {
			next_vs.add(val);
		}
		public int get(int ad) {
			return next_vs.get(ad);
		}
		public ArrayList<Integer> getAll() {
			return next_vs;
		}
		public int size() {
			return next_vs.size();
		}
		public void clear() {
			next_vs.clear();
		}
		public void addAll(Node0n vnew) {
			this.next_vs.addAll(vnew.next_vs);
		}
	}

	static class Edge {
		int from=-1, v2=-1;
		long weight;
		public Edge(int vn, long w) {
			this.v2 = vn;
			this.weight = w;
		}
		public Edge(int cm, int vn, long w) {
			this.from = cm;
			this.v2 = vn;
			this.weight = w;
		}
	}

	static class Edge2 {
		int v2;
		long cost1,cost2;
		public Edge2(int vn, long w1, long w2) {
			this.v2 = vn;
			this.cost1 = w1;
			this.cost2 = w2;
		}
	}

	static class CompEdge_float implements Comparator<Edge>{
		//今は小さいのが前に出てくる
		public int compare(Edge a, Edge b) {
			if(a.weight>b.weight) return 1;
			else if(a.weight<b.weight) return -1;
			else return a.v2-b.v2;
		}
	}
	static class Vector {
		int x,y;
		public Vector(int sx, int sy) {
			this.x=sx;
			this.y=sy;
		}
	}
}
yukicoder

結果

テストケース

ソースコード
