結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
👑  kakel-san
|
| 提出日時 | 2026-11-12 23:11:47 |
| 言語 | C# (.NET 10.0.403 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 581 ms / 4,500 ms |
| + 890µs | |
| コード長 | 10,294 bytes |
| 記録 | |
| コンパイル時間 | 11,753 ms |
| コンパイル使用メモリ | 171,156 KB |
| 実行使用メモリ | 126,392 KB |
| 最終ジャッジ日時 | 2026-11-12 23:12:12 |
| 合計ジャッジ時間 | 24,433 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (228 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net10.0/main.dll main -> /home/judge/data/code/bin/Release/net10.0/publish/
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (n, m, q) = (c[0], c[1], c[2]);
var map = NArr(m);
var query = NArr(q);
var (idlist, ctree) = MergeCycle(n, map);
var hld = new HeavyLightDecomposition(ctree, 0);
var score = new PriorityQueue<int, int>[ctree.Length];
var scpos = new Dictionary<int, int>();
var seg = new AtCoder.Segtree<int, SegOp>(ctree.Length);
var ans = new List<int>();
foreach (var que in query)
{
if (que[0] == 1)
{
var segpos = hld.Id[idlist[que[1] - 1]];
scpos[que[2]] = segpos;
if (score[segpos] == null) score[segpos] = new PriorityQueue<int, int>();
score[segpos].Enqueue(que[2], -que[2]);
if (que[2] == score[segpos].Peek()) seg[segpos] = que[2];
}
else
{
var sid = idlist[que[1] - 1];
var tid = idlist[que[2] - 1];
var max = GetMax(hld, seg, sid, tid);
if (max > 0)
{
ans.Add(max);
var maxpos = scpos[max];
score[maxpos].Dequeue();
if (score[maxpos].Count > 0) seg[maxpos] = score[maxpos].Peek();
else seg[maxpos] = 0;
}
else ans.Add(-1);
}
}
WriteLine(string.Join("\n", ans));
}
static int GetMax(HeavyLightDecomposition hld, AtCoder.Segtree<int, SegOp> seg, int s, int t)
{
var scur = s;
var tcur = t;
var sid = hld.Id[scur];
var tid = hld.Id[tcur];
var max = 0;
while (hld.Head[scur] != hld.Head[tcur])
{
if (sid > tid)
{
max = Math.Max(max, seg.Prod(hld.Id[hld.Head[scur]], sid + 1));
scur = hld.Parent[hld.Head[scur]];
sid = hld.Id[scur];
}
else
{
max = Math.Max(max, seg.Prod(hld.Id[hld.Head[tcur]], tid + 1));
tcur = hld.Parent[hld.Head[tcur]];
tid = hld.Id[tcur];
}
}
return Math.Max(max, seg.Prod(Math.Min(sid, tid), Math.Max(sid, tid) + 1));
}
static (int[] idlist, List<int>[] ctree) MergeCycle(int n, int[][] map)
{
var tree = new List<int>[n];
for (var i = 0; i < n; ++i) tree[i] = new List<int>();
foreach (var edge in map)
{
tree[edge[0] - 1].Add(edge[1] - 1);
tree[edge[1] - 1].Add(edge[0] - 1);
}
var scc = new SCCGraph(n);
var visited = new bool[n];
DFS(0, -1, tree, scc, visited);
var conn = scc.SCC();
var idlist = new int[n];
for (var i = 0; i < conn.Length; ++i)
{
foreach (var ci in conn[i]) idlist[ci] = i;
}
var csets = new HashSet<int>[conn.Length];
for (var i = 0; i < csets.Length; ++i) csets[i] = new HashSet<int>();
for (var i = 0; i < n; ++i) foreach (var next in tree[i])
{
if (idlist[i] != idlist[next]) csets[idlist[i]].Add(idlist[next]);
}
var ctree = new List<int>[conn.Length];
for (var i = 0; i < ctree.Length; ++i) ctree[i] = [.. csets[i]];
return (idlist, ctree);
}
static void DFS(int cur, int prev, List<int>[] tree, SCCGraph scc, bool[] visited)
{
visited[cur] = true;
foreach (var next in tree[cur])
{
if (prev == next) continue;
scc.AddEdge(cur, next);
if (!visited[next]) DFS(next, cur, tree, scc, visited);
}
}
class SCCGraph
{
private int _n;
private List<(int from, int to)> edges;
public SCCGraph(int n)
{
_n = n;
edges = new List<(int, int)>();
}
public int NumVertices() { return _n; }
public void AddEdge(int from, int to) { edges.Add((from, to )); }
public (int, int[]) SCCIds()
{
var g = new CSR<int>(_n, edges);
var nowOrd = 0;
var groupNum = 0;
var visited = new List<int>(_n);
var low = new int[_n];
var ord = Enumerable.Repeat(-1, _n).ToArray();
var ids = new int[_n];
void DFS(int v)
{
low[v] = ord[v] = nowOrd++;
visited.Add(v);
for (var i = g.Start[v]; i < g.Start[v + 1]; ++i)
{
var to = g.EList[i];
if (ord[to] == -1)
{
DFS(to);
low[v] = Math.Min(low[v], low[to]);
}
else low[v] = Math.Min(low[v], ord[to]);
}
if (low[v] == ord[v])
{
while (true)
{
var u = visited.Last();
visited.RemoveAt(visited.Count - 1);
ord[u] = _n;
ids[u] = groupNum;
if (u == v) break;
}
++groupNum;
}
}
for (var i = 0; i < _n; ++i) if (ord[i] == -1) DFS(i);
for (var i = 0; i < ids.Length; ++i) ids[i] = groupNum - 1 - ids[i];
return (groupNum, ids);
}
public List<int>[] SCC()
{
var (groupNum, list) = SCCIds();
var counts = new int[groupNum];
foreach (var x in list) ++counts[x];
var groups = new List<int>[groupNum];
for (var i = 0; i < groups.Length; ++i) groups[i] = new List<int>(counts[i]);
for (var i = 0; i < _n; ++i) groups[list[i]].Add(i);
return groups;
}
}
// 有向辺のリスト
class CSR<E>
{
public int[] Start { get; private set; }
public E[] EList { get; private set; }
public CSR(int n, List<(int, E)> edges)
{
Start = new int[n + 1];
EList = new E[edges.Count];
foreach (var e in edges) ++Start[e.Item1 + 1];
for (var i = 1; i <= n; ++i) Start[i] += Start[i - 1];
var counter = (int[])Start.Clone();
foreach (var e in edges)
{
EList[counter[e.Item1]++] = e.Item2;
}
}
}
/// <summary>
/// 木のHLD(重軽分解)を行う
/// </summary>
class HeavyLightDecomposition
{
// 訪問順に頂点の番号を記載 セグメント木などをこの順に格納すればHeavyPathについてのクエリに答えられる
public int[] Vertex;
// 頂点ごとに訪問番号を記載 頂点iがHeavyPath上で何番目にあるかは Id[i]-Id[Head[i]] で取得できる
// Id,Head,CCount,Parentのインデックスは、作成時に与えられた番号であることに注意
public int[] Id;
// HeavyPathのルートとなる頂点番号
public int[] Head;
// 部分木のサイズ
public int[] CCount;
// 親頂点番号
public int[] Parent;
public HeavyLightDecomposition(List<int>[] tree, int root)
{
var n = tree.Length;
Vertex = new int[n];
Id = new int[n];
Head = new int[n];
CCount = new int[n];
Parent = new int[n];
Parent[root] = -1;
DFS1(-1, root, tree);
var count = 0;
DFS2(-1, root, tree, root, ref count);
}
void DFS1(int prev, int cur, List<int>[] tree)
{
++CCount[cur];
foreach (var next in tree[cur])
{
if (prev == next) continue;
Parent[next] = cur;
DFS1(cur, next, tree);
CCount[cur] += CCount[next];
}
}
void DFS2(int prev, int cur, List<int>[] tree, int head, ref int count)
{
Vertex[count] = cur;
Id[cur] = count;
++count;
Head[cur] = head;
var maxcc = 0;
var maxcid = -1;
foreach (var next in tree[cur])
{
if (prev == next) continue;
if (maxcc < CCount[next])
{
maxcc = CCount[next];
maxcid = next;
}
}
if (maxcid >= 0) DFS2(cur, maxcid, tree, head, ref count);
foreach (var next in tree[cur])
{
if (prev == next || maxcid == next) continue;
DFS2(cur, next, tree, next, ref count);
}
}
// HLD上での最小共通祖先を求める
public int LCA(int uid, int vid)
{
while (Head[uid] != Head[vid])
{
// u,vの所属するHeavy Pathが異なる場合、行きがけ順が後のほうをさかのぼる
if (uid > vid)
{
uid = Parent[Head[uid]];
}
else
{
vid = Parent[Head[vid]];
}
}
return Math.Min(uid, vid);
}
}
struct SegOp : AtCoder.ISegtreeOperator<int>
{
public int Identity => 0;
public int Operate(int x, int y)
{
return Math.Max(x, y);
}
}
}