結果

問題 No.529 帰省ラッシュ
ユーザー f1b_maxbl00df1b_maxbl00d
提出日時 2020-04-17 12:58:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 499 ms / 4,500 ms
コード長 10,017 bytes
コンパイル時間 2,487 ms
コンパイル使用メモリ 162,820 KB
実行使用メモリ 52,576 KB
最終ジャッジ日時 2024-04-14 12:35:32
合計ジャッジ時間 8,858 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 328 ms
34,784 KB
testcase_09 AC 329 ms
32,272 KB
testcase_10 AC 373 ms
33,804 KB
testcase_11 AC 374 ms
34,172 KB
testcase_12 AC 227 ms
31,892 KB
testcase_13 AC 278 ms
52,576 KB
testcase_14 AC 312 ms
42,684 KB
testcase_15 AC 494 ms
37,888 KB
testcase_16 AC 499 ms
37,796 KB
testcase_17 AC 417 ms
50,428 KB
testcase_18 AC 426 ms
50,812 KB
testcase_19 AC 426 ms
47,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
struct Gedge {
	LL src,to;
	T cost;
	Gedge(LL s,LL t, T c) :src(s),to(t), cost(c) {}
	Gedge(LL t, T c) :src(-1), to(t), cost(c) {}
};

template<class T>
using WeightedGraph = vector<vector<Gedge<T>>>;
using UnweightedGraph = vector<vector<LL>>;
template<class T>
using Gedges = vector<Gedge<T>>;

//TT(T,T):=モノイドの乗算
//require Monoid
template<class T>
class Segtree {
private:
	vector<T> seg;
	LL RN;
	typedef function<T(T, T)> TT;
	TT f;
	T Me;
public:
	Segtree(LL N, TT _f,T me) {
		RN = 1;
		while (RN < N)RN *= 2;
		Me = me;
		seg.resize(2 * RN, Me);
		f = _f;
	}
	Segtree(vector<T>& V, TT _f,T me) {
		LL N = V.size();
		RN = 1;
		while (RN < N)RN *= 2;
		seg.resize(2 * RN, T());
		f = _f;
		for (LL n = 0; n < N; n++) seg[RN + n] = V[n];
		for (LL k = RN - 1; k >= 1; k--) {
			seg[k] = f(seg[2 * k], seg[2 * k + 1]);
		}
		Me = me;
	}
	//set n-th as x(0 index!!!!!)
	void set(LL n, T x) {
		seg[RN + n] = x;
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to x*p(0 index!!!!!)
	void addl(LL n, T x) {
		seg[RN + n] = f(x, seg[RN+n]);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to p*x(0 index!!!!!)
	void addr(LL n, T x) {
		seg[RN + n] = f(seg[RN + n], x);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//get [l,r] (0 index!!!!!)
	T get(LL l, LL r) {
		T ansl = Me, ansr = Me;
		r++;
		l += RN;
		r += RN;
		while (l < r) {
			if (l & 1) {
				ansl = f(ansl, seg[l]);
				l++;
			}
			if (r & 1) {
				r--;
				ansr = f(seg[r], ansr);
			}
			l >>= 1;
			r >>= 1;
		}
		return f(ansl, ansr);
	}
	//get n-th number(0 index!!!!!)
	T get(LL n) {
		return seg[RN + n];
	}
	T operator[](LL n) {
		return seg[RN + n];
	}
};

struct TNode {
	LL parent;
	VLL childs;
	TNode() :parent(-1) {};
};
using Tree = vector<TNode>;

void SetTree(UnweightedGraph& G, Tree& T, LL root = 0) {
	T.resize(G.size());
	stack<PLL> st;
	st.push(PLL(root, -1));
	while (!st.empty()) {
		LL cur = st.top().first;
		LL p = st.top().second;
		st.pop();
		T[cur].parent = p;
		for (LL ch : G[cur]) {
			if (ch == p)continue;
			T[cur].childs.push_back(ch);
			st.push(PLL(ch, cur));
		}
	}
}

struct HLDnode {
	LL depth;
	VLL nums;
	LL parent;
	VLL childs;
	LL pad;
	HLDnode() :depth(0),parent(-1),pad(0){};
};

struct HLD {
	vector<HLDnode> tree;
	vector<PLL> corres;   //corres[n]:=(u,v) <==> point n is tree[u][v]
	LL V;
	vector<PLL> eulerind;
	HLD(Tree& t, LL root = 0) {
		V = t.size();
		VLL subtrees(V, -1);
		//各部分木のサイズを求める
		{
			stack<LL> order;
			stack<LL> hold;
			hold.push(root);
			while (!hold.empty()) {
				LL cur = hold.top();
				hold.pop();
				order.push(cur);
				for (LL ch : t[cur].childs) {
					hold.push(ch);
				}
			}
			while (!order.empty()) {
				LL cur = order.top();
				order.pop();
				subtrees[cur] = 1;
				for (LL ch : t[cur].childs) {
					subtrees[cur] += subtrees[ch];
				}
			}
		}
		//HL分解 with eulertour
		{
			corres.resize(V);
			corres[root] = PLL(0, 0);
			eulerind.resize(V);
			LL cur = root;
			LL nexthld = 1;
			LL nexteuler = 0;
			tree.push_back(HLDnode());
			tree[0].nums.push_back(root);
			dfs(t, subtrees, cur, nexthld, nexteuler);
		}
	}
	void dfs(Tree& t,VLL& subtrees,LL cur, LL& nexthld,LL& nexteuler) {
		LL hld = corres[cur].first;
		eulerind[cur].first = nexteuler++;
		if (t[cur].childs.size() == 0)
		{
			eulerind[cur].second = nexteuler - 1;
			return;
		}
		LL maxsub = t[cur].childs[0];
		for (LL cn = 1; cn < t[cur].childs.size(); cn++) {
			if (subtrees[maxsub] < subtrees[t[cur].childs[cn]]) {
				maxsub = t[cur].childs[cn];
			}
		}
		tree[hld].nums.push_back(maxsub);
		corres[maxsub] = PLL(hld, tree[hld].nums.size() - 1);
		dfs(t, subtrees, maxsub, nexthld, nexteuler);
		for (LL ch : t[cur].childs) {
			if (ch == maxsub)continue;
			corres[ch] = PLL(nexthld, 0);
			tree.push_back(HLDnode());
			tree.back().depth = tree[hld].depth + 1;
			tree.back().nums.push_back(ch);
			tree.back().parent = cur;
			tree[hld].childs.push_back(nexthld++);
			LL neold = nexteuler;
			dfs(t, subtrees, ch, nexthld, nexteuler);
			tree[corres[ch].first].pad = neold;
		}
		eulerind[cur].second = nexteuler - 1;
	}
	LL LCA(LL u, LL v) {
		//uの属するnode.depth >= vの属するnode.depthにする
		if (tree[corres[u].first].depth < tree[corres[v].first].depth) {
			swap(u, v);
		}
		while (tree[corres[u].first].depth > tree[corres[v].first].depth) {
			u = tree[corres[u].first].parent;
		}
		while (corres[u].first != corres[v].first) {
			u = tree[corres[u].first].parent;
			v = tree[corres[v].first].parent;
		}
		if (corres[u].second > corres[v].second)return v;
		else return u;
	}
};

struct DFSTreeNode {
	VLL childs;
	LL ord, lowlink;
	LL dece;   //何番目の二重連結成分に含まれるか
	DFSTreeNode() : ord(-1), lowlink(-1), dece(-1) {};
};
typedef vector<DFSTreeNode> DFSTree;

void BridgeDECEdfs(UnweightedGraph& G, DFSTree& tree, LL n, LL& ord, VVLL& backedges, LL parent) {
	if (tree[n].ord != -1)return;
	tree[n].ord = ord++;
	tree[n].lowlink = tree[n].ord;
	for (LL next : G[n]) {
		if (tree[next].ord != -1) {
			//後退辺の場合
			if (next == parent)continue;
			backedges[next].push_back(n);
			tree[n].lowlink = min(tree[n].lowlink, tree[next].ord);
		}
		else {
			tree[n].childs.push_back(next);
			BridgeDECEdfs(G, tree, next, ord, backedges, n);
			tree[n].lowlink = min(tree[n].lowlink, tree[next].lowlink);
		}
	}
}

void BridgeDECE(UnweightedGraph& G, DFSTree& tree, VVLL& bridges, VVLL& dece, LL start = 0) {
	tree.resize(G.size());
	bridges.resize(G.size());
	for (LL n = 0; n < G.size(); n++)tree[n].ord = -1;
	VVLL backedges;   //backedges[i]\ni j <==> 後退辺j->iが存在
	backedges.resize(G.size());
	LL ord = 0;   //次設定するord
	//ord,lowlink求める
	BridgeDECEdfs(G, tree, start, ord, backedges, -1);
	//連結要素id
	LL id = 0;
	stack<LL> st;
	for (LL n = 0; n < G.size(); n++) {
		if (tree[n].dece != -1)continue;
		st.push(n);
		dece.push_back(VLL());
		while (!st.empty()) {
			LL cur = st.top();
			st.pop();
			if (tree[cur].dece != -1)continue;
			tree[cur].dece = id;
			dece.back().push_back(cur);
			//子
			for (LL ch : tree[cur].childs) {
				if (tree[cur].ord < tree[ch].lowlink) {
					//橋だった
					bridges[cur].push_back(ch);
				}
				else {
					st.push(ch);
				}
			}
			//後退辺
			for (LL next : backedges[cur]) {
				st.push(next);
			}
		}
		id++;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL V, E, Q;
	cin >> V >> E >> Q;
	VLL conv(V);   //各頂点がDECEでどの頂点に移るか
	Tree dtree;
	{
		UnweightedGraph G(V);
		for (LL m = 0; m < E; m++) {
			LL a, b;
			cin >> a >> b;
			a--; b--;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		DFSTree dfstree;
		VVLL bridges, dece;
		BridgeDECE(G, dfstree, bridges, dece);
		for (LL d = 0; d < dece.size();d++) {
			for (LL n : dece[d]) {
				conv[n] = d;
			}
		}
		UnweightedGraph deceg(dece.size());
		for (LL s = 0; s < V; s++) {
			for (LL t : bridges[s]) {
				LL ss = conv[s];
				LL tt = conv[t];
				deceg[ss].push_back(tt);
				deceg[tt].push_back(ss);
			}
		}
		SetTree(deceg, dtree);
	}
	HLD hld(dtree);
	vector<priority_queue<LL>> priqs(hld.V);   //各deceに来た獲物
	Segtree<PLL> seg(hld.V, [](PLL a, PLL b) {
		if (a.first > b.first)return a;
		else return b;
	},PLL(-1,-1));   //(価値、そいつがいるdece要素)
	for (LL q = 0; q < Q; q++) {
		LL type;
		cin >> type;
		if (type == 1) {
			LL U, W;
			cin >> U >> W;
			U--;
			LL decenum = conv[U];
			LL segid = hld.eulerind[decenum].first;
			LL maxold = -1;
			if(priqs[decenum].size()!= 0)maxold = priqs[decenum].top();
			priqs[decenum].push(W);
			if (maxold != priqs[decenum].top()) {
				seg.set(segid, PLL(W, decenum));
			}
		}
		else {
			LL S, T;
 			cin >> S >> T;
			LL deces = conv[--S];
			LL decet = conv[--T];
			LL lca = hld.LCA(deces, decet);
			PLL ans(-1, -1);
			LL st = hld.corres[deces].first;
			LL tt = hld.corres[decet].first;
			LL lt = hld.corres[lca].first;
			while (hld.tree[st].depth != hld.tree[lt].depth) {
				LL top = hld.tree[st].nums[0];
				ans = max(ans, seg.get(hld.eulerind[top].first, hld.eulerind[deces].first));
				deces = hld.tree[st].parent;
				st = hld.corres[deces].first;
			}
			ans = max(ans, seg.get(hld.eulerind[lca].first, hld.eulerind[deces].first));;
			while (hld.tree[tt].depth != hld.tree[lt].depth) {
				LL top = hld.tree[tt].nums[0];
				ans = max(ans, seg.get(hld.eulerind[top].first, hld.eulerind[decet].first));
				decet = hld.tree[tt].parent;
				tt = hld.corres[decet].first;
			}
			ans = max(ans, seg.get(hld.eulerind[lca].first, hld.eulerind[decet].first));;
			cout << ans.first << "\n";
			if (ans.first != -1) {
				LL segid = hld.eulerind[ans.second].first;
				priqs[ans.second].pop();
				if (priqs[ans.second].size() == 0)seg.set(segid, PLL(-1, -1));
				else {
					LL cmax = priqs[ans.second].top();
					seg.set(segid, PLL(cmax, ans.second));
				}
			}
		}
	}
	return 0;
}
0