#644783 (Java21) No.1390 Get together

提出ソース

結果

問題	No.1390 Get together
ユーザー	char-khan
提出日時	2021-04-05 12:28:27
言語	Java21 (openjdk 21)
結果	AC
実行時間	742 ms / 2,000 ms
コード長	14,606 bytes
コンパイル時間	3,639 ms
コンパイル使用メモリ	98,596 KB
実行使用メモリ	101,884 KB
最終ジャッジ日時	2024-06-09 19:35:35
合計ジャッジ時間	16,845 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	56 ms 50,560 KB
testcase_01	AC	56 ms 50,056 KB
testcase_02	AC	56 ms 50,576 KB
testcase_03	AC	102 ms 53,260 KB
testcase_04	AC	86 ms 52,908 KB
testcase_05	AC	102 ms 53,056 KB
testcase_06	AC	97 ms 52,920 KB
testcase_07	AC	86 ms 52,912 KB
testcase_08	AC	86 ms 52,012 KB
testcase_09	AC	97 ms 53,084 KB
testcase_10	AC	55 ms 50,508 KB
testcase_11	AC	52 ms 50,168 KB
testcase_12	AC	52 ms 50,696 KB
testcase_13	AC	54 ms 50,572 KB
testcase_14	AC	52 ms 50,608 KB
testcase_15	AC	53 ms 50,584 KB
testcase_16	AC	427 ms 83,820 KB
testcase_17	AC	592 ms 76,684 KB
testcase_18	AC	406 ms 97,300 KB
testcase_19	AC	669 ms 101,088 KB
testcase_20	AC	705 ms 92,492 KB
testcase_21	AC	742 ms 93,372 KB
testcase_22	AC	584 ms 96,932 KB
testcase_23	AC	566 ms 100,744 KB
testcase_24	AC	579 ms 99,452 KB
testcase_25	AC	693 ms 101,796 KB
testcase_26	AC	656 ms 101,864 KB
testcase_27	AC	662 ms 101,240 KB
testcase_28	AC	653 ms 101,884 KB
testcase_29	AC	675 ms 101,280 KB
testcase_30	AC	646 ms 101,784 KB
testcase_31	AC	661 ms 101,708 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

public class Main {
	public static void main(String[] args) {
		new Main().solve(args);
		pw.close();
	}

	/**
	 * ASCII
	 * 0 48
	 * A 65
	 * a 97
	 */

	static PrintWriter pw = new PrintWriter(System.out);

	long MOD = 1_000_000_007;
	int INF = Integer.MAX_VALUE;
	long LINF = Long.MAX_VALUE;

	public void solve(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		Map<Integer, TreeSet<Integer>> b = new HashMap<>();
		var c = new HashSet<Integer>();
		UnionFind uf = new UnionFind(N);
		for (int i = 0; i < N; i++) {
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			c.add(y);
			b.compute(x, (k, v)-> {
				if (v == null) {
					var s = new TreeSet<Integer>();
					s.add(y);
					return s;
				} else {
					if (!v.contains(y)) uf.unite(y, v.first());
					v.add(y);
					return v;
				}
			});
		}
		int count = 0;
		var p = new HashSet<Integer>();
		for (int e : c) {
			int pa = uf.find(e);
			if (!p.contains(pa)) {
				count++;
				p.add(pa);
			}
		}
		out(b.size() - count);
	}

	class Data {
		int a;
		int b;
		long c;
		Data(int x, int y, long z) {
			a = x;
			b = y;
			c = z;
		}
	}
	class SP {
		String a;
		int b;
		int c;
		SP(String x, int y, int z) {
			a = x;
			b = y;
			c = z;
		}
	}

	class IPair {
		int a;
		int b;
		IPair(int x, int y) {
			a = x;
			b = y;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + a;
			result = prime * result + b;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (obj == null) return false;
			if (getClass() != obj.getClass()) return false;
			IPair other = (IPair)obj;
			if (a != other.a) return false;
			if (b != other.b) return false;
			return true;
		}
	}

	class ILPair {
		int a;
		long b;
		ILPair(int x, long y) {
			a = x;
			b = y;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + a;
			result = (int)(b ^ (b >>> 32));
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (obj == null) return false;
			if (getClass() != obj.getClass()) return false;
			ILPair other = (ILPair)obj;
			if (a != other.a) return false;
			if (b != other.b) return false;
			return true;
		}
	}

	long modSub(long a, long b) {
		long ret = (a - Math.abs(b)) % MOD;
		if (ret < 0) ret = MOD + ret;
		return ret;
	}

	long modInv(long a, long m) {
		long b = m;
		long u = 1;
		long v = 0;
		while (b != 0) {
			long t = a / b;
			a -= t * b;
			u -= t * v;
			long tmp = a;
			a = b;
			b = tmp;
			tmp = u;
			u = v;
			v = tmp;
		}
		u %= m;
		if (u < 0) u += m;
		return u;
	}




	boolean inRange(int y, int x, int H, int W) {
		return 0 <= y && y < H && 0 <= x && x < W;
	}



	double getD(double x1, double x2, double y1, double y2) {
		return Math.sqrt(Math.pow(x1-x2,2) + Math.pow(y1-y2, 2));
	}



	static int[][] d4 = new int[][] {{1,0},{0,1},{-1,0},{0,-1}};
	static int[][] d8 = new int[][] {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

	long binarySearch(long max, Predicate<Long> predicate) {
		long low = -1;
		long high = max;

		while (high - low > 1) {
			long mid = high - (high - low) / 2;
			if (predicate.test(mid)) high = mid;
			else low = mid;
		}
		return high;
	}


	// Binary Indexed Tree
	// http://hos.ac/slides/20140319_bit.pdf
	class BIT {
		int n;
		int[] bit = new int[1000010];

		BIT(int n) {
			this.n = n;
		}

		void add(int a, int w) {
			for (int x = a; x <= n; x += (x & -x)) bit[x] += w;
		}
		int sum(int a) {
			int ret = 0;
			for (int x = a; x > 0; x -= (x & -x)) ret += bit[x];
			return ret;
		}
	}

	class Dijkstra {
		DNode[] nodes;

		Dijkstra(DNode[] nodes) {
			this.nodes = nodes;
		}

		long[] get(int start) {
			long[] costs = new long[nodes.length];
			Arrays.fill(costs, Long.MAX_VALUE);
			costs[start] = 0;
			var queue = new PriorityQueue<Distance>();
			queue.add(new Distance(start, 0));
			while (!queue.isEmpty()) {
				var d = queue.poll();
				if (d.cost > costs[d.dest]) continue;
				for (var neighbor : nodes[d.dest].neighbors) {
					long nextCost = neighbor.cost + costs[d.dest];
					if (nextCost < costs[neighbor.dest]) {
						costs[neighbor.dest] = nextCost;
						queue.add(new Distance(neighbor.dest, nextCost));
					}
				}
			}
			return costs;
		}


	}

	class DNode {
		List<Distance> neighbors;

		DNode() {
			neighbors = new ArrayList<Distance>();
		}

		DNode(List<Distance> neighbors) {
			this.neighbors = neighbors;
		}
	}

	class Distance implements Comparable<Distance> {
		int dest;
		long cost;
		Distance(int dest, long cost) {
			this.dest = dest;
			this.cost = cost;
		}

		@Override
		public int compareTo(Distance another) {
			return Long.compare(cost, another.cost);
		}
	}


	// https://algo-logic.info/prime-fact/
	class PrimeFact {
		int[] spf;
		PrimeFact(int N) {
			spf = new int[N+1];
			for (int i = 0; i <= N; i++) spf[i] = i;
			for (int i = 2; i * i <= N; i++) {
				if (spf[i] == i) {
					for (int j = i * i; j <= N; j += i) {
						if (spf[j] == j) {
							spf[j] = i;
						}
					}
				}
			}
		}

		Map<Integer, Integer> getMap(int num) {
			var map = new HashMap<Integer, Integer>();
			while (num != 1) {
				map.compute(spf[num], (k, v) -> v == null ? 1 : v+1);
				num /= spf[num];
			}
			return map;
		}

		int getDivisorNum(int num) {
			int s = 1;
			while (num != 1) {
				int count = 1;
				int pf = spf[num];
				while (num % pf == 0) {
					count++;
					num /= pf;
				}
				s *= count;
			}
			return s;
		}
	}

	@SuppressWarnings("unchecked")
	class SegmentTree<T> {
		int n = 1;
		Object[] node;
		BinaryOperator<T> op;
		T fill;

		SegmentTree(T[] ary, T fill, BinaryOperator<T> op) {
			this.op = op;
			this.fill = fill;
			int size = ary.length;
			while(n < size) n *= 2;
			node = new Object[2*n - 1];
			Arrays.fill(node, fill);
			for (int i = 0; i < size; i++) node[i+n-1] = ary[i];
			for (int i = n-2; i >= 0; i--) node[i] = op.apply((T)node[2*i+1], (T)node[2*i+2]);
		}

		void update(int i, T value) {
			i += n - 1;
			node[i] = value;
			while(i > 0) {
				i = (i - 1) / 2;
				node[i] = op.apply((T)node[2*i+1], (T)node[2*i+2]);
			}
		}

		T get(int a, int b) {
			return get(a, b, 0, 0, n);
		}

		T get(int a, int b, int k, int l, int r) {
			if (r <= a || b <= l) return fill;
			if (a <= l && r <= b) return (T)node[k];
			T lc = get(a, b, 2*k+1, l, (l+r)/2);
			T rc = get(a, b, 2*k+2, (l+r)/2, r);
			return op.apply(lc, rc);
		}
	}

	class Permutation {
		int[] array;

		Permutation(int N) {
			array = new int[N];
			for (int i = 0; i < N; i++) {
				array[i] = i+1;
			}
		}

		boolean nextPermutation() {
		    int i = array.length - 1;
		    while (i > 0 && array[i - 1] >= array[i])
		        i--;
		    if (i <= 0)
		        return false;

		    int j = array.length - 1;
		    while (array[j] <= array[i - 1])
		        j--;
		    int temp = array[i - 1];
		    array[i - 1] = array[j];
		    array[j] = temp;

		    j = array.length - 1;
		    while (i < j) {
		        temp = array[i];
		        array[i] = array[j];
		        array[j] = temp;
		        i++;
		        j--;
		    }
		    return true;
		}
	}

	class UnionFind {
		int[] parents;
		int[] counts;

		public UnionFind(int size) {
			parents = new int[size];
			counts = new int[size];
			for (int i = 0; i < size; i++) {
				parents[i] = i;
				counts[i] = 1;
			}
		}

		public int find(int a) {
			if (parents[a] == a) return a;
			parents[a] = find(parents[a]);
			return parents[a];
		}

		public void unite(int a, int b) {
			a = find(a);
			b = find(b);
			if (a == b) return;
			if (counts[a] < counts[b]) {
				parents[a] = b;
				counts[b] += counts[a];
			} else {
				parents[b] = a;
				counts[a] += counts[b];
			}
		}

		public boolean differ(int a, int b) {
			a = find(a);
			b = find(b);
			return a != b;
		}

		public int count(int a) {
			return counts[find(a)];
		}

		public List<List<Integer>> getTrees() {
			var map = new HashMap<Integer, List<Integer>>();
			for (int i = 0; i < parents.length; i++) {
				List<Integer> list = map.computeIfAbsent(parents[i],k -> new ArrayList<Integer>());
				list.add(i);
			}
			return new ArrayList<>(map.values());
		}
	}

	class Combination {
		final int mod;
		final int max;

		final long[] fact;
		final long[] inv;
		final long[] invfact;

		public Combination(int n) {
			this(n, 1_000_000_007);
		}

		public Combination(int n, int mod) {
			this.mod = mod;
			max = n + 1;
			fact = new long[max];
			invfact = new long[max];
			inv = new long[max];

			inv[1] = 1;
			for (int i = 2; i < inv.length; i++) {
				inv[i] = inv[mod % i] * (mod - mod / i) % mod;
			}

			fact[0] = 1;
			invfact[0] = 1;
			for (int i = 1; i < inv.length; i++) {
				fact[i] = i * fact[i - 1] % mod;
				invfact[i] = inv[i] * invfact[i - 1] % mod;
			}
		}

		public long get(int n, int r) {
			return fact[n] * invfact[n - r] % mod * invfact[r] % mod;
		}

		public long gcd(long a, long b) {
			if (b == 0) return a;
			else {
				b %= MOD;
				if (b < 0) b+=MOD;
				return gcd(b, (b-a*inv[(int)b]%MOD*b%MOD)%MOD);
			}
		}
	}

	public long gcd(long a, long b) {
		if (b == 0) return a;
		else return gcd(b, a%b);
	}

	public long getInv(long a) {
		long b = MOD, u = 1, v = 0;
		while (b > 0) {
			long t = a / b;
			a -= t * b;
			long tmp = a;
			a = b;
			b = tmp;
			u -= t * v;
			tmp = u;
			u = v;
			v = tmp;
		}
		u %= MOD;
		if (u < 0) u += MOD;
		return u;
	}


	public long modPow(long base, long exponent) {
		return modPow(base, exponent, MOD);
	}

	// 繰り返し二乗法
	public long modPow(long base, long exponent, long mod) {
		if (exponent == 0) return 1;
		long ret = 1;
		while (exponent > 0) {
			if ((exponent & 1) == 1) ret = ret * base % mod;
			base = base * base % mod;
			exponent >>= 1;
		}
		return ret;
	}

	public long choose(long n, long m) {
		long deno = 1;
		long nume = 1;
		m = (n - m < m ? n - m : m);
		for (long i = 1; i <= m; i++) {
			deno = deno * (n - i + 1) % MOD;
			nume = nume * i % MOD;
		}
		return deno * getInv(nume) % MOD;
	}

	public void reverse(int[] a) {
		int last = a.length-1;
		int n = a.length / 2;
		for (int i = 0; i < n; i++) {
			int t = a[i];
			a[i] = a[last-i];
			a[last-i] = t;
		}
	}

	public void reverse(long[] a) {
		int last = a.length-1;
		int n = a.length / 2;
		for (int i = 0; i < n; i++) {
			long t = a[i];
			a[i] = a[last-i];
			a[last-i] = t;
		}
	}

	void fout(Object... args) {
		StringBuilder sb = new StringBuilder();
		for (Object arg : args) {
			sb.append(arg.toString());
			sb.append(" ");
		}
		out(sb.toString());
	}

	void out() {
		pw.println();
	}

	void out(String a) {
		pw.println(a);
	}
	void out(boolean a) {
		pw.println(a);
	}

	void out(int a) {
		pw.println(a);
	}

	void out(long a) {
		pw.println(a);
	}

	void out(double a) {
		pw.println(a);
	}

	void out(char a) {
		pw.println(a);
	}

	void rout(String a) {
		out(a);
		pw.close();
		System.exit(0);
	}
	void rout(int a) {
		out(a);
		pw.close();
		System.exit(0);
	}
	void rout(long a) {
		out(a);
		pw.close();
		System.exit(0);
	}
	void rout(double a) {
		out(a);
		pw.close();
		System.exit(0);
	}
	void rout(char a) {
		out(a);
		pw.close();
		System.exit(0);
	}

}



class FastScanner {
    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 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 char[] nextCA() {
    	return next().toCharArray();
    }

    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 double nextDouble() {
        return Double.parseDouble(next());
    }

    public int[] ia(int N) {
    	int[] a = new int[N];
    	for (int i = 0; i < N; i++) a[i] = this.nextInt();
    	return a;
    }
    public long[] la(int N) {
    	long[] a = new long[N];
    	for (int i = 0; i < N; i++) a[i] = this.nextLong();
    	return a;
    }
    public double[] da(int N) {
    	double[] a = new double[N];
    	for (int i = 0; i < N; i++) a[i] = this.nextDouble();
    	return a;
    }
    public boolean[][] bgrid(int H, int W, char c) {
    	boolean[][] a = new boolean[H][W];
    	for (int i = 0; i < H; i++) {
    		char[] s = this.nextCA();
    		for (int j = 0; j < W; j++) a[i][j] = s[j] == c;
    	}
    	return a;
    }
}

yukicoder

結果

テストケース

ソースコード