結果

問題 No.1727 [Cherry 3rd Tune] Stray
ユーザー chocorusk
提出日時 2021-09-13 22:12:52
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,260 bytes
コンパイル時間 2,426 ms
コンパイル使用メモリ 77,352 KB
実行使用メモリ 54,228 KB
最終ジャッジ日時 2024-10-07 08:54:16
合計ジャッジ時間 4,156 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//FastScanner scanner=new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=scanner.nextInt();
		UnionFind uf=new UnionFind(1<<(2*n));
		for(int i=0; i<(1<<(2*n)); i++) {
			int x=0, y=0;
			for(int j=0; j<n; j++) {
				if((i&(1<<j))!=0) {
					if(j==n-1) x^=1;
					else x^=(1<<(j+1));
					y^=(1<<(j+n));
				}
				if((i&(1<<(j+n)))!=0) {
					if(j==0) x^=(1<<(2*n-1));
					else x^=(1<<(j-1+n));
					y^=(1<<j);
				}
			}
			uf.unite(i, x);
			uf.unite(i, y);
		}
		out.println(uf.cmp);
		scanner.close();
		out.close();
	}
}
class UnionFind{
	int n;
	int[] par;
	int cmp;
	public UnionFind(int n) {
		this.n=n;
		this.par=new int[n];
		Arrays.fill(this.par, -1);
		this.cmp=n;
	}
	public int find(int x) {
		if(par[x]<0) return x;
		return par[x]=find(par[x]);
	}
	public boolean unite(int x, int y) {
		x=find(x);
		y=find(y);
		if(x==y) {
			return false;
		}
		cmp--;
		if(par[x]>par[y]) {
			int tmp=x;
			x=y;
			y=tmp;
		}
		par[x]+=par[y];
		par[y]=x;
		return true;
	}
	public boolean same(int x, int y) {
		return find(x)==find(y);
	}
}
0