結果
問題 | No.529 帰省ラッシュ |
ユーザー | f1b_maxbl00d |
提出日時 | 2020-04-17 12:51:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,104 bytes |
コンパイル時間 | 2,548 ms |
コンパイル使用メモリ | 165,880 KB |
実行使用メモリ | 53,036 KB |
最終ジャッジ日時 | 2024-10-03 10:13:54 |
合計ジャッジ時間 | 7,762 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | WA | - |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
ソースコード
#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 != W) { 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; LL pad,r; while (hld.tree[st].depth != hld.tree[lt].depth) { pad = hld.tree[st].pad; r = hld.corres[deces].second; ans = max(ans, seg.get(pad, pad + r)); deces = hld.tree[st].parent; st = hld.corres[deces].first; } pad = hld.tree[lt].pad; LL l = hld.corres[lca].second; r = hld.corres[deces].second; ans = max(ans, seg.get(pad + l, pad + r)); while (hld.tree[tt].depth != hld.tree[lt].depth) { pad = hld.tree[tt].pad; r = hld.corres[decet].second; ans = max(ans, seg.get(pad, pad + r)); decet = hld.tree[tt].parent; tt = hld.corres[decet].first; } pad = hld.tree[lt].pad; l = hld.corres[lca].second; r = hld.corres[decet].second; ans = max(ans, seg.get(pad + l, pad + r)); 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; }