結果
問題 |
No.3025 Chocol∀te
|
ユーザー |
|
提出日時 | 2025-03-05 23:59:07 |
言語 | C# (.NET 8.0.404) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,401 bytes |
コンパイル時間 | 14,119 ms |
コンパイル使用メモリ | 172,552 KB |
実行使用メモリ | 91,880 KB |
最終ジャッジ日時 | 2025-03-05 23:59:35 |
合計ジャッジ時間 | 26,157 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 1 -- * 76 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (109 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.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) = (c[0], c[1]); var map = NArr(m); var a = NList; var q = NN; var query = NArr(q); var tree = new HashSet<int>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new HashSet<int>(); var tmax = new int[n]; foreach (var edge in map) { tree[edge[0] - 1].Add(edge[1] - 1); tree[edge[1] - 1].Add(edge[0] - 1); ++tmax[edge[0] - 1]; ++tmax[edge[1] - 1]; } var sq = (int)Math.Sqrt(q); var count = new long[n]; var ans = new List<long>(); for (var i = 0; i < q; i += sq) { for (var j = 0; j < n; ++j) { count[j] = 0; foreach (var next in tree[j]) count[j] += a[next]; } var clist = new List<int>(); for (var j = i; j < q && j < i + sq; ++j) if (query[j][0] == 3) clist.Add(query[j][1] - 1); for (var j = i; j < q && j < i + sq; ++j) { if (query[j][0] == 1) { var u = query[j][1] - 1; var v = query[j][2] - 1; if (tree[u].Contains(v)) { tree[u].Remove(v); if (tree[u].Count > 10 && tree[u].Count < tmax[u] / 2) { tree[u] = new HashSet<int>(tree[u]); tmax[u] = tree[u].Count; } tree[v].Remove(u); if (tree[v].Count > 10 && tree[v].Count < tmax[v] / 2) { tree[v] = new HashSet<int>(tree[v]); tmax[v] = tree[v].Count; } count[u] -= a[v]; count[v] -= a[u]; } else { tree[u].Add(v); tmax[u] = Math.Max(tmax[u], tree[u].Count); tree[v].Add(u); tmax[v] = Math.Max(tmax[v], tree[v].Count); count[u] += a[v]; count[v] += a[u]; } } else if (query[j][0] == 2) { var p = query[j][1] - 1; var na = query[j][2]; foreach (var ci in clist) if (tree[ci].Contains(p)) { count[ci] += na - a[p]; } a[p] = na; } else { ans.Add(count[query[j][1] - 1]); } } } WriteLine(string.Join("\n", ans)); } }