結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0