結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 raven7959
|
| 提出日時 | 2022-09-02 10:55:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,008 bytes |
| コンパイル時間 | 3,665 ms |
| コンパイル使用メモリ | 242,448 KB |
| 実行使用メモリ | 40,588 KB |
| 最終ジャッジ日時 | 2024-11-15 16:17:40 |
| 合計ジャッジ時間 | 9,592 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 3 ms
5,248 KB |
| testcase_02 | AC | 3 ms
5,248 KB |
| testcase_03 | AC | 3 ms
5,248 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 | AC | 174 ms
19,732 KB |
| testcase_13 | AC | 247 ms
40,588 KB |
| testcase_14 | AC | 276 ms
27,648 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | AC | 300 ms
38,624 KB |
| testcase_18 | AC | 299 ms
38,940 KB |
| testcase_19 | WA | - |
ソースコード
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n"
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vld = vector<long double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvs = vector<vector<string>>;
using vvc = vector<vector<char>>;
using vvd = vector<vector<double>>;
using vvld = vector<vector<long double>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int INF = 1e9;
const ll LINF = 2e18;
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
bool ispow2(int i) { return i && (i & -i) == i; }
bool ispow2(ll i) { return i && (i & -i) == i; }
template <class T>
vector<T> make_vec(size_t a) {
return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
for (int i = 0; i < int(v.size()); i++) {
is >> v[i];
}
return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
for (int i = 0; i < int(v.size()); i++) {
os << v[i];
if (i < int(v.size()) - 1) os << ' ';
}
return os;
}
static uint32_t RandXor(){
static uint32_t x=123456789;
static uint32_t y=362436069;
static uint32_t z=521288629;
static uint32_t w=88675123;
uint32_t t;
t=x^(x<<11);
x=y; y=z; z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
static long double Rand01(){
return (RandXor()+0.5)*(1.0/UINT_MAX);
}
template <typename T = int>
struct Edge{
int from, to;
T cost;
int idx;
Edge() = default;
Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}
operator int() const { return to; }
};
template <typename T = int>
struct Graph{
vector<vector<Edge<T>>> g;
int es;
Graph() = default;
explicit Graph(int n) : g(n), es(0) {}
size_t size() const{
return g.size();
}
void add_directed_edge(int from, int to, T cost = 1){
g[from].emplace_back(from, to, cost, es++);
}
void add_edge(int from, int to, T cost = 1){
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void read(int M, int padding = -1, bool weighted = false, bool directed = false){
for (int i = 0; i < M; i++){
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (directed) add_directed_edge(a, b, c);
else add_edge(a, b, c);
}
}
inline vector<Edge<T>> &operator[](const int &k){
return g[k];
}
inline const vector<Edge<T>> &operator[](const int &k) const{
return g[k];
}
};
template <typename T = int>
using Edges = vector<Edge<T>>;
template<typename T>
vector<int> bridge_tree_decomposition(Graph<T> &G){
int N=(int)G.g.size();
vector<bool> visited(N);
vector<int> ord(N),low(N),cmp(N,-1);
int ts=0,idx=0;
auto dfs=[&](auto &&self,int v,int p=-1)->void{
visited[v]=true;
ord[v]=ts;
low[v]=ord[v];
ts++;
bool flg=false;
for(auto nv:G[v]){
if(!visited[nv]){
self(self,nv,v);
low[v]=min(low[v],low[nv]);
}
else if(nv!=p){
low[v]=min(low[v],ord[nv]);
}
else{
if(!flg) flg=true;
else low[v]=min(low[v],ord[p]);
}
}
};
auto dfs2=[&](auto &&self,int v)->void{
for(auto nv:G[v]){
if(cmp[nv]!=-1) continue;
if(low[nv]<=ord[v]) cmp[nv]=cmp[v];
else{
cmp[nv]=idx;
idx++;
}
self(self,nv);
}
};
for(int i=0;i<N;i++) if(!visited[i]) dfs(dfs,i);
for(int i=0;i<N;i++){
if(cmp[i]==-1){
cmp[i]=idx;
idx++;
dfs2(dfs2,i);
}
}
return cmp;
}
// HeavyLightDecomposition<Graph<int>> HLD(g,root); などする,rootは指定しない場合0になる
// size: 部分木のサイズ(元の木の頂点番号->サイズ)
// depth: 深さ(元の木の頂点番号->深さ)
// down: 行きがけ順(セグ木上での順番でもある) (元の木の頂点番号->行きがけ順)
// up: 部分木クエリに使うやつ
// nxt: ある頂点が属する連結成分の中で最も浅い頂点(元の木の頂点番号->元の木の頂点番号)
// par: 親の番号(元の木の頂点番号->元の木の頂点番号)
// rev: 行きがけ順から元の木の頂点番号に戻す配列
// void path_query(int u,int v,bool vertex,F f): u,vパスについての可換なクエリを処理,頂点属性ならvertexをtrueにする
// void path_noncommutative_query(int u,int v,bool vertex,F f): u,vパスについての非可換なクエリを処理,頂点属性ならvertexをtrueにする
// void subtree_query(int u,bool vertex,F f): uを根とする部分木についてのクエリを処理
// 上3つではいずれもラムダ式でfを渡せばよく,[l,r)についての結果をどこかにまとめる感じで書くと良い
// その他,汎用的な関数がある(lca,la,dist,in_subtree,move)
template <typename G>
struct HeavyLightDecomposition{
private:
void dfs_sz(int cur){
size[cur] = 1;
for (auto &dst : g[cur]){
if (dst == par[cur]){
if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]);
else continue;
}
depth[dst] = depth[cur] + 1;
par[dst] = cur;
dfs_sz(dst);
size[cur] += size[dst];
if (size[dst] > size[g[cur][0]]) swap(dst, g[cur][0]);
}
}
void dfs_hld(int cur){
down[cur] = id++;
rev[down[cur]] = cur;
for (auto dst : g[cur]){
if (dst == par[cur]) continue;
nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst));
dfs_hld(dst);
}
up[cur] = id;
}
// [u, v)
vector<pair<int, int>> ascend(int u, int v) const{
if(u == v) return {};
vector<pair<int, int>> res;
while (nxt[u] != nxt[v]){
res.emplace_back(down[u], down[nxt[u]]);
u = par[nxt[u]];
}
if (u != v) res.emplace_back(down[u], down[v] + 1);
return res;
}
// (u, v]
vector<pair<int, int>> descend(int u, int v) const{
if (u == v) return {};
if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
auto res = descend(u, par[nxt[v]]);
res.emplace_back(down[nxt[v]], down[v]);
return res;
}
public:
G &g;
int id;
vector<int> size, depth, down, up, nxt, par, rev;
HeavyLightDecomposition(G &_g, int root = 0)
: g(_g),
id(0),
size(g.size(), 0),
depth(g.size(), 0),
down(g.size(), -1),
up(g.size(), -1),
nxt(g.size(), root),
par(g.size(), root),
rev(g.size(), root)
{
dfs_sz(root);
dfs_hld(root);
}
void build(int root){
dfs_sz(root);
dfs_hld(root);
}
pair<int, int> idx(int i) const { return make_pair(down[i], up[i]); }
template <typename F>
void path_query(int u, int v, bool vertex, const F &f){
int l = lca(u, v);
for (auto &&[a, b] : ascend(u, l)){
int s = a + 1, t = b;
s > t ? f(t, s) : f(s, t);
}
if (vertex) f(down[l], down[l] + 1);
for (auto &&[a, b] : descend(l, v)){
int s = a, t = b + 1;
s > t ? f(t, s) : f(s, t);
}
}
template <typename F>
void path_noncommutative_query(int u, int v, bool vertex, const F &f){
int l = lca(u, v);
for (auto &&[a, b] : ascend(u, l)) f(a + 1, b);
if (vertex) f(down[l], down[l] + 1);
for (auto &&[a, b] : descend(l, v)) f(a, b + 1);
}
template <typename F>
void subtree_query(int u, bool vertex, const F &f){
f(down[u] + int(!vertex), up[u]);
}
int lca(int a, int b){
while (nxt[a] != nxt[b]){
if (down[a] < down[b]) swap(a, b);
a = par[nxt[a]];
}
return depth[a] < depth[b] ? a : b;
}
int lca(int r, int u, int v){
return lca(r, u) ^ lca(u, v) ^ lca(v, r);
}
int la(int v, int k) {
while(1){
int u = nxt[v];
if(down[v] - k >= down[u]) return rev[down[v] - k];
k -= down[v] - down[u] + 1;
v = par[nxt[u]];
}
}
int dist(int a, int b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; }
// bがaの部分木内にあるか
bool in_subtree(int a, int b) { return down[a] <= down[b] && down[b] <= up[a]; }
// aからbの方向に1進んだ頂点を返す
int move(int a, int b) {
assert(a != b);
if(in_subtree(b,a)){
return par[a];
}
else{
if(lca(a,b)==a){
return la(b,dist(a,b)-1);
}
else{
return par[a];
}
}
}
// s-tパス上にxがあるか
bool in_path(int s, int t, int x){
return dist(s, x) + dist(x, t) == dist(s, t);
}
};
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
struct segtree{
public:
segtree() : segtree(0) {}
segtree(int n) : _n(n) {
log = ceil_pow2(_n);
size = 1 << log;
pq=vector<priority_queue<int>>(size);
d=vector<pii>(2*size);
rep(i,_n) d[size+i].second=i;
rep(i,size) add(i,-1);
}
void add(int p,int x){
pq[p].emplace(x);
d[p+size].first=pq[p].top();
p+=size;
for (int i = 1; i <= log; i++){
int x=p>>i;
if(d[2*x].first>=d[2*x+1].first) d[x]=d[2*x];
else d[x]=d[2*x+1];
}
}
void erase(int p){
pq[p].pop();
d[p+size].first=pq[p].top();
p+=size;
for (int i = 1; i <= log; i++){
int x=p>>i;
if(d[2*x].first>=d[2*x+1].first) d[x]=d[2*x];
else d[x]=d[2*x+1];
}
}
pii prod(int l, int r){
assert(0 <= l && l <= r && r <= _n);
pii ret(-1,-1);
l += size;
r += size;
while (l < r){
if (l & 1){
if(ret.first<d[l].first) ret=d[l];
l++;
}
if (r & 1){
r--;
if(ret.first<d[r].first) ret=d[r];
}
l >>= 1;
r >>= 1;
}
return ret;
}
private:
int _n, size, log;
vector<priority_queue<int>> pq;
vector<pii> d;
};
void solve(){
int N,M,Q;
cin>>N>>M>>Q;
vi A(M),B(M);
Graph<int> original_graph(N);
rep(i,M){
cin>>A[i]>>B[i];
A[i]--; B[i]--;
original_graph.add_edge(A[i],B[i]);
}
auto ret=bridge_tree_decomposition(original_graph);
int X=*max_element(all(ret))+1;
Graph<int> G(X);
rep(i,M){
if(ret[A[i]]!=ret[B[i]]){
G.add_edge(ret[A[i]],ret[B[i]]);
}
}
HeavyLightDecomposition<Graph<int>> HLD(G,0);
segtree seg(X);
while(Q--){
int t;
cin>>t;
if(t==1){
int u,w;
cin>>u>>w;
u--;
seg.add(ret[u],w);
}
else{
int s,t;
cin>>s>>t;
s--; t--;
s=ret[s]; t=ret[t];
pii tmp(-1,-1);
auto f=[&](int l,int r)->void{
auto x=seg.prod(l,r);
if(x.first>tmp.first) tmp=x;
};
HLD.path_query(s,t,true,f);
cout<<tmp.first<<"\n";
if(tmp.first!=-1) seg.erase(tmp.second);
}
}
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}