結果

問題 No.3309 Aging Railway
コンテスト
ユーザー さかさのさかな
提出日時 2025-10-25 17:35:08
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,460 ms / 3,000 ms
コード長 1,643 bytes
コンパイル時間 3,252 ms
コンパイル使用メモリ 87,100 KB
実行使用メモリ 96,724 KB
最終ジャッジ日時 2025-10-25 17:35:38
合計ジャッジ時間 29,079 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no3309;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		UnionFind uf = new UnionFind(n);
		int[] a = new int[n];
		int[] b = new int[n];
		int[] s = new int[m];
		int[] t = new int[m];
		for(int i = 0;i < n - 1;i++) {
			a[i] = sc.nextInt() - 1;
			b[i] = sc.nextInt() - 1; 
		}for(int i = 0;i < m;i++) {
			s[i] = sc.nextInt() - 1;
			t[i] = sc.nextInt() - 1;
		}int[][] p = new int[n][n];
		for(int i = n - 2;i >= 0;i--) {
			uf.unite(a[i], b[i]);
			for(int j = 0;j < n;j++) {
				p[i][j] = uf.getRoot(j);
			}
		}StringBuilder sb = new StringBuilder();
		int[] ans = new int[n];
		for(int i = 0;i < m;i++) {
			int left = 0;
			int right = n - 1;
			while(left < right - 1) {
				int mid = (left + right)/2;
				if(p[mid][s[i]] == p[mid][t[i]]) {
					left = mid;
				}else {
					right = mid;
				}
			}ans[left]++;
		}for(int i = n - 1;i >= 1;i--) {
			ans[i - 1] += ans[i];
		}
		for(int i = 1;i < n;i++) {
			sb.append(ans[i] + "\n");
		}
		System.out.print(sb);
		
	}public static class UnionFind{
		int[] root;
		int n;
		public UnionFind(int m) {
			n = m;
			root = new int[n + 1];
			for(int i = 0;i <= n;i++) {
				root[i] = i;
			}
		}public void unite(int a,int b) {
			int x = getRoot(a);
			int y = getRoot(b);
			root[y] = root[x];
		}
		public int getRoot(int ind) {
			if(root[ind] != ind) {
				root[ind] = getRoot(root[ind]);
			}return root[ind];
		}public boolean same(int a,int b) {
			return getRoot(a) == getRoot(b);
		}
	}

}
0