結果

問題 No.1030 だんしんぐぱーりない
ユーザー 紙ぺーぱー紙ぺーぱー
提出日時 2020-04-17 22:10:50
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 672 ms / 2,000 ms
コード長 8,564 bytes
コンパイル時間 3,715 ms
コンパイル使用メモリ 120,728 KB
実行使用メモリ 68,728 KB
最終ジャッジ日時 2024-04-14 14:23:33
合計ジャッジ時間 19,892 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
27,036 KB
testcase_01 AC 34 ms
28,328 KB
testcase_02 AC 34 ms
26,288 KB
testcase_03 AC 32 ms
24,872 KB
testcase_04 AC 32 ms
26,108 KB
testcase_05 AC 497 ms
60,420 KB
testcase_06 AC 386 ms
56,640 KB
testcase_07 AC 228 ms
40,992 KB
testcase_08 AC 246 ms
49,788 KB
testcase_09 AC 450 ms
64,144 KB
testcase_10 AC 160 ms
33,852 KB
testcase_11 AC 362 ms
52,632 KB
testcase_12 AC 452 ms
56,676 KB
testcase_13 AC 374 ms
57,088 KB
testcase_14 AC 448 ms
57,572 KB
testcase_15 AC 196 ms
40,220 KB
testcase_16 AC 387 ms
50,636 KB
testcase_17 AC 457 ms
63,688 KB
testcase_18 AC 477 ms
58,856 KB
testcase_19 AC 243 ms
39,692 KB
testcase_20 AC 303 ms
46,320 KB
testcase_21 AC 355 ms
56,904 KB
testcase_22 AC 318 ms
49,280 KB
testcase_23 AC 347 ms
48,312 KB
testcase_24 AC 263 ms
39,800 KB
testcase_25 AC 317 ms
51,280 KB
testcase_26 AC 202 ms
33,556 KB
testcase_27 AC 227 ms
34,160 KB
testcase_28 AC 420 ms
53,684 KB
testcase_29 AC 387 ms
56,280 KB
testcase_30 AC 317 ms
50,192 KB
testcase_31 AC 294 ms
45,780 KB
testcase_32 AC 413 ms
54,876 KB
testcase_33 AC 456 ms
60,256 KB
testcase_34 AC 168 ms
39,280 KB
testcase_35 AC 665 ms
68,728 KB
testcase_36 AC 672 ms
66,672 KB
testcase_37 AC 666 ms
66,800 KB
testcase_38 AC 671 ms
68,592 KB
testcase_39 AC 664 ms
64,512 KB
testcase_40 AC 33 ms
27,192 KB
testcase_41 AC 33 ms
28,408 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using Debug = System.Diagnostics.Trace;
using SB = System.Text.StringBuilder;
using static System.Math;

using Number = System.Int64;
using static System.Numerics.BigInteger;
namespace Program {
	public class Solver {
		Random rnd = new Random(0);
		public void Solve() {
			var n = ri;
			var k = ri;
			var q = ri;
			var val = Enumerate(n, x => rl);
			var pos = Enumerate(k, x => ri - 1);

			var G = Enumerate(n, x => new List<int>());
			var hl = new HLTree(n);
			var ord = new int[n];
			var rev = new int[n];
			for (int i = 0; i < n - 1; i++) {
				var u = ri - 1; var v = ri - 1;
				G[v].Add(u);
				hl.AddEdge(u, v);
			}
			hl.Build(0);
			var ptr = 0;
			Action<int> dfs = null;
			dfs = (cur) => {
				rev[ptr] = cur;
				ord[cur] = ptr++;
				foreach (var t in G[cur]) {
					val[t] = Max(val[t], val[cur]);
					dfs(t);
				}
			};
			dfs(0);
			Debug.WriteLine(val.AsJoinedString());
			var min = new RmQ(k);
			var max = new RMQ(k);
			for (int i = 0; i < k; i++) {
				min.Update(i, ord[pos[i]]);
				max.Update(i, ord[pos[i]]);
			}
			for (int i = 0; i < q; i++) {
				if (ri == 1) {
					var p = ri - 1;
					var v = ri - 1;
					pos[p] = v;
					min.Update(p, ord[pos[p]]);
					max.Update(p, ord[pos[p]]);
				}
				else {
					var l = ri - 1;
					var r = ri;
					var mi = min.Query(l, r);
					var ma = max.Query(l, r);
					var lca = hl.GetLCA(rev[mi], rev[ma]);
					Console.WriteLine(val[lca]);
				}
			}

		}
		const long INF = 1L << 60;
		static int[] dx = { -1, 0, 1, 0 };
		static int[] dy = { 0, 1, 0, -1 };
		int ri { get { return sc.Integer(); } }
		long rl { get { return sc.Long(); } }
		double rd { get { return sc.Double(); } }
		string rs { get { return sc.Scan(); } }
		public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
		static T[] Enumerate<T>(int n, Func<int, T> f) {
			var a = new T[n]; for (int i = 0; i < a.Length; ++i) a[i] = f(i); return a;
		}
		static T[][] Enumerate<T>(int n, int m, Func<int, int, T> f) {
			return Enumerate(n, x => Enumerate(m, y => f(x, y)));
		}
		static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
	}
}

#region main
static class Ex {
	static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
	static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
		return string.Join(st, ie);
	}
	static public void Main() {
		Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
		var solver = new Program.Solver();
		var t = new System.Threading.Thread(solver.Solve, 100000000);
		t.Start();
		t.Join();
		//*/
		//solver.Solve();
		Console.Out.Flush();
	}
}
#endregion
#region Ex
namespace Program.IO {
	using System.IO;
	using System.Text;
	using System.Globalization;

	public class Printer : StreamWriter {
		public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
		public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
	}

	public class StreamScanner {
		public StreamScanner(Stream stream) { str = stream; }

		public readonly Stream str;
		private readonly byte[] buf = new byte[1024];
		private int len, ptr;
		public bool isEof = false;
		public bool IsEndOfStream { get { return isEof; } }

		private byte read() {
			if (isEof) return 0;
			if (ptr >= len) {
				ptr = 0;
				if ((len = str.Read(buf, 0, 1024)) <= 0) {
					isEof = true;
					return 0;
				}
			}
			return buf[ptr++];
		}

		public char Char() {
			byte b = 0;
			do b = read(); while ((b < 33 || 126 < b) && !isEof);
			return (char)b;
		}
		public string Scan() {
			var sb = new StringBuilder();
			for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
			return sb.ToString();
		}
		public string ScanLine() {
			var sb = new StringBuilder();
			for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
			return sb.ToString();
		}
		public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
		public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
		public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
	}
}

#endregion

//Segment Tree

#region SegTree Operator
public interface IData<T> {
	T Merge(T l, T r);
	T Identity { get; }
	T InitValue { get; }
}
#endregion
#region Segment Tree

public class SegmentTree<T, U>
   where U : struct, IData<T> {
	int sz;
	int n;
	T[] data;
	U op;
	public SegmentTree(int size) {
		sz = size;
		n = 1;
		while (n < size) n *= 2;
		data = new T[n * 2];
		for (int i = 0; i < data.Length; i++)
			data[i] = op.InitValue;
	}
	public SegmentTree(T[] a) {
		sz = a.Length;
		n = 1;
		while (n < sz) n *= 2;
		data = new T[n * 2];
		for (int i = 0; i < n; i++)
			data[i + n] = (i < a.Length) ? a[i] : op.InitValue;
		for (int i = n - 1; i >= 0; i--)
			data[i] = op.Merge(data[i * 2], data[i * 2 + 1]);
	}
	public void Update(int k, T v) {
		k += n;
		data[k] = v;
		for (k = k / 2; k > 0; k /= 2)
			data[k] = op.Merge(data[k * 2], data[k * 2 + 1]);

	}
	public T Query(int a, int b) { return query(a, b, 1, 0, n); }
	private T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)
			return op.Identity;
		if (a <= l && r <= b)
			return data[k];
		else {
			var vl = query(a, b, k * 2, l, (l + r) / 2);
			var vr = query(a, b, k * 2 + 1, (l + r) / 2, r);
			return op.Merge(vl, vr);
		}
	}
	public T[] Items {
		get {
			var ret = new T[sz];
			for (int i = 0; i < sz; i++)
				ret[i] = data[i + n];
			return ret;
		}
	}

}
#endregion
#region RmQ
public class RmQ : SegmentTree<long, MinData> {
	public RmQ(int size) : base(size) { }
}
public struct MinData : IData<long> {
	public long InitValue { get { return 0; } }
	public long Identity { get { return long.MaxValue; } }
	public long Merge(long l, long r) { return Math.Min(l, r); }


}
#endregion
#region RMQ
public class RMQ : SegmentTree<long, MaxData> {
	public RMQ(int size) : base(size) { }
}
public struct MaxData : IData<long> {
	public long Identity { get { return long.MinValue; } }

	public long InitValue { get { return 0; } }

	public long Merge(long l, long r) { return Math.Max(l, r); }
}
#endregion
#region HLTree
public class HLTree {
	int n;
	List<int>[] G;
	int[] subtreeSize;
	int[] maxsize;
	int[] par;
	int[] d;

	Chain[] go;
	int[] pos;
	List<Chain> chains;
	public HLTree(int N) {
		n = N;
		G = new List<int>[n];
		chains = new List<Chain>();
		for (int i = 0; i < n; i++)
			G[i] = new List<int>();
		subtreeSize = new int[n];
		maxsize = new int[n];
		par = new int[n];
		d = new int[n];
		go = new Chain[n];
		pos = new int[n];
	}
	public void AddEdge(int u, int v) {
		G[u].Add(v); G[v].Add(u);
	}
	public void Build(int root = 0) {
		computeSubtreeSize(root);
		Decomposite(-1, root, 0);

	}
	void computeSubtreeSize(int r) {
		var stack = new Stack<int>();
		stack.Push(r);
		var iter = new int[n];
		par[r] = -1;
		//dfs
		while (stack.Count > 0) {
			var cur = stack.Peek();
			if (iter[cur] == G[cur].Count) {
				stack.Pop();
				subtreeSize[cur]++;
				if (par[cur] != -1) {
					subtreeSize[par[cur]] += subtreeSize[cur];
					maxsize[par[cur]] = Math.Max(maxsize[par[cur]], subtreeSize[cur]);
				}
				continue;
			}
			var next = G[cur][iter[cur]++];
			if (next == par[cur]) continue;
			par[next] = cur;
			d[next] = d[cur] + 1;
			stack.Push(next);
		}

	}
	void Decomposite(int from, int cur, int lv) {
		var chain = new Chain(from, lv);
		chains.Add(chain);
		chain.Add(cur);
		while (cur != from) {
			var next = cur;
			go[cur] = chain;
			pos[cur] = chain.Count;
			foreach (var to in G[cur]) {
				if (to == from) continue;
				if (maxsize[cur] == subtreeSize[to]) {
					maxsize[cur] = -1;
					next = to;
					chain.Add(to);
				}
				else Decomposite(cur, to, lv + 1);
			}

			from = cur;
			cur = next;

		}
		chain.Init();

	}
	public int GetLCA(int u, int v) {
		while (go[u] != go[v]) {
			if (go[u].Level < go[v].Level) v = go[v].From;
			else u = go[u].From;
		}
		if (d[u] <= d[v]) return u;
		else return v;
	}


}
public class Chain {
	const bool DEBUG = true;
	public int From { get; set; }
	public int Level { get; set; }
	public int Count { get; private set; }
	List<int> heavy;
	public Chain(int from, int lv) {
		From = from;
		Level = lv;
		heavy = new List<int>();
	}
	public void Add(int v) {
		if (DEBUG)
			heavy.Add(v);
		Count++;
	}
	public void Init() {

	}
}
#endregion
0