結果

問題 No.529 帰省ラッシュ
ユーザー rgw2010
提出日時 2025-03-17 20:51:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 580 ms / 4,500 ms
コード長 4,792 bytes
コンパイル時間 3,423 ms
コンパイル使用メモリ 230,380 KB
実行使用メモリ 81,720 KB
最終ジャッジ日時 2025-03-17 20:51:30
合計ジャッジ時間 11,181 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define ctz(x) __builtin_ctz(x)
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, m, q, op, u, v, cnt, sum;
int dfn[N], low[N], fa[N], dep[N], rdfn[N], son[N], siz[N], top[N], id[N];
stack<int> T;
vector<pair<int, int>> E[N];
vector<int> G[N];
set<pair<int, int>> S;
inline void add(int u, int v, int id){
	E[u].push_back({v, id});
}
inline void add(int u, int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
inline void tarjan(int u, int fa){
	dfn[u] = low[u] = ++cnt;
	T.push(u);
	for(auto t : E[u]){
		int v = t.fi, w = t.se;
		if(w == (fa ^ 1))
		  continue;
		if(!dfn[v]){
			tarjan(v, w);
			low[u] = min(low[u], low[v]);
		}
		else
		  low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]){
		++sum;
		id[u] = sum;
		while(T.top() != u){
			id[T.top()] = sum;
			T.pop();
		}
		T.pop();
	}
}
inline void dfs1(int u, int f){
	siz[u] = 1;
	for(auto v : G[u]){
		if(v == f)
		  continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])
		  son[u] = v;
	}
}
inline void dfs2(int u, int k){
	dfn[u] = ++cnt;
	rdfn[cnt] = u;
	top[u] = k;
	if(!son[u])
	  return ;
	dfs2(son[u], k);
	for(auto v : G[u]){
		if(v == fa[u] || v == son[u])
		  continue;
		dfs2(v, v);
	}
}
namespace Tree{
	struct Node{
		int l, r;
		int Max, id;
		priority_queue<int> S;
	}X[N << 2];
	inline void pushup(int k){
		X[k].Max = max(X[k << 1].Max, X[k << 1 | 1].Max);
		if(X[k << 1].Max == X[k].Max)
		  X[k].id = X[k << 1].id;
		else
		  X[k].id = X[k << 1 | 1].id;
	}
	inline void build(int k, int l, int r){
		X[k].l = l, X[k].r = r;
		X[k].Max = -1;
		if(l == r){
			X[k].id = l;
			return ;
		}
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
		pushup(k);
	}
	inline void update(int k, int i, int v){
		if(X[k].l == i && i == X[k].r){
			X[k].S.push(v);
			X[k].Max = X[k].S.top();
//			cerr << "now1:" << i << ' ' << X[k].Max << '\n';
			return ;
		}
		int mid = (X[k].l + X[k].r) >> 1;
		if(i <= mid)
		  update(k << 1, i, v);
		else
		  update(k << 1 | 1, i, v);
		pushup(k);
	}
	inline void del(int k, int i){
		if(X[k].l == i && i == X[k].r){
//			cerr << "Yes " << ' ' << i << ' ' << X[k].S.size() << '\n';;
			X[k].S.pop();
			if(X[k].S.empty())
			  X[k].Max = -1;
			else
			  X[k].Max = X[k].S.top();
//			cerr << X[k].Max << ' ' << X[k].S.size() << '\n';
			return ;
		}
		int mid = (X[k].l + X[k].r) >> 1;
		if(i <= mid)
		  del(k << 1, i);
		else
		  del(k << 1 | 1, i);
		pushup(k);		
	}
	inline pair<int, int> ask(int k, int l, int r){
		if(X[k].l == l && r == X[k].r)
		  return {X[k].Max, X[k].id};
		int mid = (X[k].l + X[k].r) >> 1;
		if(r <= mid)
		  return ask(k << 1, l, r);
		else if(l > mid)
		  return ask(k << 1 | 1, l, r);
		else{
			auto x = ask(k << 1, l, mid), y = ask(k << 1 | 1, mid + 1, r);
			if(x.fi >= y.fi)
			  return x;
			else
			  return y;
		}
	}
};
inline int query(int u, int v){
	int Max = -1, id = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])
		  swap(u, v);
		auto t = Tree::ask(1, dfn[top[u]], dfn[u]);
		if(t.fi > Max){
			Max = t.fi;
			id = t.se;
		}
		u = fa[top[u]];
	}
	if(dep[u] > dep[v])
	  swap(u, v);
	auto t = Tree::ask(1, dfn[u], dfn[v]);
	if(t.fi > Max){
		Max = t.fi;
		id = t.se;
	}
//	cerr << id << '\n';
	if(id)
	  Tree::del(1, id);
	return Max;
}
int main(){
	n = read(), m = read(), q = read();
	for(int u, v, i = 1; i <= m; ++i){
		u = read(), v = read();
		add(u, v, i << 1);
		add(v, u, i << 1 | 1);
	}
	for(int i = 1; i <= n; ++i)
	  if(!dfn[i])
	    tarjan(i, 0);
	for(int u = 1; u <= n; ++u){
		for(auto t : E[u]){
			int v = t.fi;
			if(id[u] == id[v] || S.count({id[u], id[v]}) || S.count({id[v], id[u]}))
			  continue;
			S.insert({id[u], id[v]});
			add(id[u], id[v]);
		}
	}
	cnt = 0;
	dfs1(1, 1);
	dfs2(1, 1);
	Tree::build(1, 1, cnt);
	while(q--){
		op = read(), u = read(), v = read();
		if(op == 1)
		  Tree::update(1, dfn[id[u]], v);
		else{
			write(query(id[u], id[v]));
			putchar('\n');
		}
//		cerr << "lst: " << Tree::X[1].id << '\n';
	}
	return 0;
}
0