結果

問題 No.3309 Aging Railway
コンテスト
ユーザー tobisatis
提出日時 2025-10-24 22:31:53
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 663 ms / 3,000 ms
コード長 2,019 bytes
コンパイル時間 8,125 ms
コンパイル使用メモリ 169,616 KB
実行使用メモリ 78,468 KB
最終ジャッジ日時 2025-10-24 22:32:16
合計ジャッジ時間 17,822 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (107 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
string String()
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return _input[_iter++];
}
T I<T>() where T : IParsable<T> => T.Parse(String(), null);
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

var n = I<int>();
var m = I<int>();
var edges = Range(n - 1, () => (I<int>() - 1, I<int>() - 1));
var passengers = Range(m, () => (I<int>() - 1, I<int>() - 1));

var ufz = new UnionFind[n - 1];
for (var i = n - 2; i >= 0; i--)
{
    var uf = new UnionFind(n);
    for (var j = n - 2; j >= i; j--)
    {
        var (u, v) = edges[j];
        uf.Union(u, v);
    }
    ufz[i] = uf;
}
var ans = new int[n - 1];
foreach (var (u, v) in passengers)
{
    var pass = -1;
    var fail = n - 1;
    while (Math.Abs(pass - fail) >= 2)
    {
        var mid = (pass + fail) >> 1;
        var uf = ufz[mid];
        if (uf.Find(u) == uf.Find(v)) pass = mid;
        else fail = mid;
    }
    if (pass > 0) ans[pass - 1]++;
}
for (var j = n - 2; j > 0; j--) ans[j - 1] += ans[j];
Console.WriteLine(string.Join(Environment.NewLine, ans));

class UnionFind
{
    int[] Verticals { get; set; }
    public UnionFind(int verticals)
    {
        Verticals = new int[verticals];
        for (int i = 0; i < verticals; i++) Verticals[i] = -1;
    }

    public int Union(int x, int y)
    {
        (x, y) = (Find(x), Find(y));
        var (sx, sy) = (Size(x), Size(y));
        if (sx < sy) (x, y, sy) = (y, x, sx);
        var (nx, ny) = (Verticals[x], Verticals[y]);
        if (x != y)
        {
            ny = x;
            nx -= sy;
        }
        (Verticals[y], Verticals[x]) = (ny, nx);
        return x;
    }

    public int Find(int x)
    {
        var pid = Verticals[x];
        if (pid < 0) return x;
        var aid = Find(pid);
        Verticals[x] = aid;
        return aid;
    }
    public int Size(int x) => -Verticals[Find(x)];
}
0