結果
問題 | No.529 帰省ラッシュ |
ユーザー |
![]() |
提出日時 | 2017-06-09 23:37:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 708 ms / 4,500 ms |
コード長 | 11,494 bytes |
コンパイル時間 | 2,331 ms |
コンパイル使用メモリ | 146,972 KB |
実行使用メモリ | 50,008 KB |
最終ジャッジ日時 | 2024-12-16 06:35:18 |
合計ジャッジ時間 | 10,744 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>#include <functional>#include <set>#include <ctime>#include <random>#include <chrono>#include <cassert>#include <tuple>#include <utility>using namespace std;namespace {using Integer = long long; //__int128;template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}template<class T> istream& operator , (istream& is, T& val){ return is >> val;}template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":""); return os;}template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}template<class H> void print(const H& head){ cout << head; }template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }template<class H> void eprint(const H& head){ cerr << head; }template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v),step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ?val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ returnrange_iterator(start_, step_); } range_iterator end(){ return range_iterator( end_, step_); } };inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexedmt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss <<v[i]; } return ss.str(); }inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }}constexpr long long mod = 9_ten + 7;struct edge{int to;int id;};class Bridge{int size;vector<vector<edge>> G;vector<int> v;vector<bool> is_bridge;int num_bridge;public:vector<pair<int,int>> bridge;vector<int> component;vector<vector<int>> new_Graph;//pre-calcvoid first_dfs(int pos, vector<bool>& visit, vector<bool>& used){if(visit[pos]){v[pos]--;return;}visit[pos] = true;for(int i=0; i<G[pos].size(); i++){edge& next = G[pos][i];if(used[next.id]) continue;if(visit[next.to]) v[pos]++;used[next.id] = true;first_dfs(next.to, visit, used);}}//imos finding-bridgeint second_dfs(int pos, vector<bool>& visit){visit[pos] = true;int ret = v[pos];for(int i=0; i<G[pos].size(); i++){int next = G[pos][i].to;if(visit[next]) continue;int tmp = second_dfs(next, visit);ret += tmp;if(tmp == 0){is_bridge[G[pos][i].id] = true;num_bridge++;bridge.push_back({pos, next});}}return ret;}//get components that each node belong tovoid third_dfs(int pos, int c, vector<bool>& visit){visit[pos] = true;for(int i=0; i<G[pos].size(); i++){edge& next = G[pos][i];if(is_bridge[next.id]) continue;if(visit[next.to]) continue;third_dfs(next.to, c, visit);}component[pos] = c;}Bridge(vector<vector<edge>>& g, int e_size) :G(g),size(g.size()),v(g.size()),is_bridge(e_size, false),num_bridge(0){vector<bool> visit(size, false);vector<bool> used(e_size, false);for(int i=0; i<size; i++){if(visit[i]) continue;first_dfs(i, visit, used);}fill(visit.begin(), visit.end(), false);for(int i=0; i<size; i++){if(visit[i]) continue;second_dfs(i, visit);}component.resize(size, -1);fill(visit.begin(), visit.end(), false);int num_components = 0;for(int i=0; i<size; i++){if(visit[i]) continue;third_dfs(i, num_components, visit);num_components++;}//decomposited graph//this is a "forest"new_Graph.resize(num_components);for(int i=0; i<bridge.size(); i++){int u = bridge[i].first;int v = bridge[i].second;new_Graph[component[u]].push_back(component[v]);new_Graph[component[v]].push_back(component[u]);}}};class HeavyLightDecomposition{public:struct heavy_set{vector<int> element;int depth;int parent_vertex;heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){}};vector<vector<int>>& G;vector<heavy_set> S;vector<int> subtree_size;vector<int> set_index;vector<int> ele_index;private:int get_subtree_size(int pos, int par){int sz = 1;for(int ch : G[pos]){if(ch == par) continue;sz += get_subtree_size(ch, pos);}return subtree_size[pos] = sz;}void make_path(int pos, int par, int set_id){set_index[pos] = set_id;ele_index[pos] = S[set_id].element.size()-1;int largest_child = -1;int value = 0;for(int ch : G[pos]){if(ch == par) continue;if(value < subtree_size[ch]){value = subtree_size[ch];largest_child = ch;}}for(int ch : G[pos]){if(ch == par) continue;if(largest_child == ch){S[set_id].element.push_back(ch);make_path(ch, pos, set_id);}else{S.emplace_back( ch, S[set_id].depth+1, pos );make_path(ch, pos, S.size()-1);}}}void init(int root){subtree_size.resize(G.size(), 0);get_subtree_size(root,root);set_index.resize(G.size(), 0);ele_index.resize(G.size(), 0);S.emplace_back( root,0,root );make_path( root, root, 0 );subtree_size.clear();}public:HeavyLightDecomposition(vector<vector<int>>& G_, int root = 0) : G(G_){init(root);}//set_index, element_index//S[set_index].element[element_index] == vpair<int,int> get_position(int v){return {set_index[v], ele_index[v]};}};template<class Value = int>class SegmentTree{int n;vector<Value> V;Value DEFAULT_VALUE;//evaluation functionstatic Value default_evaluate(Value a, Value b){return max(a,b);}function< Value(Value, Value) > evaluate;//return evaluated value in [a,b)//T[at] covers [l,r)Value RangeEvaluation(int a, int b, int at, int l, int r){//out of rangeif(r <= a || b <= l) return DEFAULT_VALUE;//coveredif(a <= l && r <= b) return V[at];//partially coveredelse{Value val_left = RangeEvaluation(a,b, at*2+1, l, (l+r)/2);Value val_right = RangeEvaluation(a,b, at*2+2, (l+r)/2, r);return evaluate(val_left, val_right);}}public:SegmentTree(int size, Value DEFAULT = 0, function< Value(Value, Value) > eval = default_evaluate){DEFAULT_VALUE = DEFAULT;evaluate = eval;n=1;while(n<size) n <<= 1;V = vector<Value>(2*n - 1, DEFAULT_VALUE);}void update(int at, Value new_val){at += n-1;V[at] = new_val;while(at>0){at = (at-1)/2;V[at] = evaluate(V[at*2 + 1], V[at*2 + 2]);}}//return evaluated value in [l,r)Value RangeEvaluation(int l, int r){if(l>=r) return DEFAULT_VALUE;if(l>=n) return DEFAULT_VALUE;return RangeEvaluation(l,r, 0, 0, n);}};int LCA(HeavyLightDecomposition& T, int u, int v){auto pu = T.get_position(u);auto pv = T.get_position(v);if(pu.first == pv.first){return pu.second < pv.second ? u : v;}if(T.S[pu.first].depth > T.S[pv.first].depth){swap(pu, pv);swap(u,v);}while(T.S[pu.first].depth != T.S[pv.first].depth){v = T.S[pv.first].parent_vertex;pv = T.get_position( v );}while(pu.first != pv.first){u = T.S[pu.first].parent_vertex;v = T.S[pv.first].parent_vertex;pu = T.get_position(u);pv = T.get_position(v);if(T.S[pv.first].depth == 0) break;if(T.S[pv.first].depth == 0) break;}if(pu.first == pv.first){return pu.second < pv.second ? u : v;}else{abort();}return -1;}int main(){int n,m,q;cin >> n,m,q;vector<vector<edge>> G(n);for(int i : range(m)){int a,b;cin >> a,b;a--; b--;G[a].push_back( edge{b, i} );G[b].push_back( edge{a, i} );}Bridge B(G, m);vector<vector<int>>& g = B.new_Graph;vector<int>& c = B.component;vector<priority_queue<int>> z(g.size());HeavyLightDecomposition h(g);vector<SegmentTree<int>> seg;seg.reserve(h.S.size());for(int i=0; i<h.S.size(); i++){seg.emplace_back( h.S[i].element.size() );}map<int, int> memo;for(int i=0; i<q; i++){int t;cin >> t;if(t==1){int u,w;cin >> u,w;u--;u = c[u];memo[w] = u;z[ u ].push(w);auto p = h.get_position( u );int s_i = p.first;int e_i = p.second;seg[s_i].update( e_i, z[u].top() );}else if(t==2){int s,t;cin >> s,t;s--; t--;s = c[s];t = c[t];int p = LCA(h, s,t);int mx = 0;for(int j=0; j<2; j++){while(h.get_position(s).first != h.get_position(p).first){auto pp = h.get_position(s);auto s_i = pp.first;auto e_i = pp.second;int tmp = seg[s_i].RangeEvaluation(0, e_i+1);mx = max(mx, tmp);s = h.S[s_i].parent_vertex;}{auto ps = h.get_position(s);auto pp = h.get_position(p);int tmp = seg[ps.first].RangeEvaluation( pp.second, ps.second+1 );mx = max(mx, tmp);}swap(s,t);}if(mx == 0){println(-1);}else{int u = memo[mx];z[u].pop();auto p = h.get_position( u );int s_i = p.first;int e_i = p.second;seg[s_i].update( e_i, z[u].size()==0 ? 0 : z[u].top() );println(mx);}}else{println("unko");abort();}}return 0;}