結果

問題 No.529 帰省ラッシュ
ユーザー momoyuumomoyuu
提出日時 2023-03-22 17:09:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 566 ms / 4,500 ms
コード長 4,812 bytes
コンパイル時間 3,753 ms
コンパイル使用メモリ 260,740 KB
実行使用メモリ 34,152 KB
最終ジャッジ日時 2024-09-18 14:59:16
合計ジャッジ時間 11,082 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
9,728 KB
testcase_01 AC 7 ms
9,728 KB
testcase_02 AC 7 ms
9,728 KB
testcase_03 AC 7 ms
9,728 KB
testcase_04 AC 15 ms
10,112 KB
testcase_05 AC 15 ms
9,984 KB
testcase_06 AC 15 ms
9,856 KB
testcase_07 AC 14 ms
9,856 KB
testcase_08 AC 514 ms
23,808 KB
testcase_09 AC 505 ms
22,912 KB
testcase_10 AC 496 ms
22,408 KB
testcase_11 AC 499 ms
22,460 KB
testcase_12 AC 448 ms
24,448 KB
testcase_13 AC 343 ms
34,152 KB
testcase_14 AC 489 ms
28,928 KB
testcase_15 AC 555 ms
21,852 KB
testcase_16 AC 566 ms
21,860 KB
testcase_17 AC 531 ms
30,692 KB
testcase_18 AC 544 ms
30,900 KB
testcase_19 AC 535 ms
28,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

template< typename T >
struct segtree{
    using F = function<T(T,T)>;
    int n;
    F f;
    T e;
    vector<T> data;
    /*
     * n:鬆らせ謨ｰ
     * f:貍皮ｮ・     * e:蜊倅ｽ榊・
     */
    segtree(int n,F f,T e):f(f),e(e){
        this->n = 1;
        while(this->n<n) (this->n)<<=1;
        data.assign(2*(this->n),e);
    }

    void set(vector<T> &a){
        for(int i = 0;i<n;i++){
            data[i+n-1] = a[i];
        }
    }

    void set(int i,T x){
        data[i+n-1] = x;
    }

    void build(){
        for(int i = n - 2;i>=0;i--){
            data[i] = f(data[2*i+1],data[2*i+2]);
        }
    }

    void update(int i,T x){
        int ni = i + n - 1;
        data[ni] = x;
        while(ni>0){
            ni = (ni-1)/2;
            data[ni] = f(data[2*ni+1],data[2*ni+2]);
        }
    }

    T query(int a,int b){
        T ans = e;
        a += n-1;
        b--;b += n-1;
        while(a>=0&&b>=0&&a<=b){
            if(a==b){
                ans = f(ans,data[a]);
                break;
            }
            if(!(a&1))ans = f(ans,data[a]);
            if(b&1)ans = f(ans,data[b]);
            a++;b--;
            a = (a-1)/2;b = (b-1)/2;
        }
        return ans;
    }

    T operator[](const int i) const {
        return data[i+n-1];
    }
};

pair<int,int> c1(pair<int,int> a,pair<int,int> b){
    return max(a,b);
}
const int inf = 1e9 + 10;
const int mx = 2e5 + 10;
int n,m,q;
vector<int> g[mx];
vector<pair<int,int> >bridge;
int vis[mx],in[mx],out[mx],head[mx],par[mx],sz[mx];
int cmp[mx],ord[mx],low[mx];
priority_queue<int> que[mx];
void dfs(int ni,int p,int&time){
    vis[ni] = 1;
    ord[ni] = low[ni] = time++;
    for(auto&to:g[ni])if(to!=p){
        if(vis[to]){
            low[ni] = min(low[ni],ord[to]);
        }else{
            dfs(to,ni,time);
            low[ni] = min(low[ni],low[to]);
            if(low[to]>ord[ni])bridge.push_back(make_pair(to,ni));
        }
    }
}

void dfs1(int ni,int p,int now){
    vis[ni] = 1;
    cmp[ni] = now;
    for(auto&to:g[ni])if(to!=p){
        if(ord[ni]<low[to]||ord[to]<low[ni]) continue;
        if(vis[to]) continue;
        dfs1(to,ni,now);
    }
}

int sdfs(int ni,int p){
    sz[ni] = 1;
    par[ni] = p;
    if(g[ni][0]==p) swap(g[ni][0],g[ni].back());
    for(auto&to:g[ni])if(to!=p){
        sz[ni] += sdfs(to,ni);
        if(sz[to]>sz[g[ni][0]]) swap(to,g[ni][0]);
    }
    return sz[ni];
}

void hdfs(int ni,int p,int &time){
    in[ni] = time++;
    for(auto&to:g[ni])if(to!=p){
        head[to] = (g[ni][0]==to?head[ni]:to);
        hdfs(to,ni,time);
    }
    out[ni] = time;
}


int main(){
    cin>>n>>m>>q;
    for(int i = 0;i<m;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int time = 0;
    dfs(0,-1,time);
    for(int i = 0;i<n;i++) vis[i] = 0;
    int now = 0;
    for(int i = 0;i<n;i++) if(vis[i]==0){
        dfs1(i,-1,now++);
    }
    assert(now-1==bridge.size());
    for(int i = 0;i<now;i++) g[i].clear();
    for(auto itr:bridge){
        int u,v;
        tie(u,v) = itr;
        u = cmp[u];
        v = cmp[v];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    time = 0;
    sdfs(0,-1);
    hdfs(0,-1,time);
    segtree<pair<int,int> >seg(now,c1,make_pair(-inf,0));
    seg.build();
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int u,w;
            cin>>u>>w;
            u--;
            u = cmp[u];
            int nn = seg[in[u]].first;
            if(nn<w){
                seg.update(in[u],make_pair(w,in[u]));
                if(nn!=-inf) que[in[u]].push(nn);
            }else que[in[u]].push(w);
        }else{
            int u,v;
            cin>>u>>v;
            u--;v--;
            u = cmp[u];
            v = cmp[v];
            int ans = -inf;
            int ni = 0;
            for(;;v=par[head[v]]){
                if(in[u]>in[v]) swap(u,v);
                if(head[u]==head[v]) break;
                auto itr = seg.query(in[head[v]],in[v]+1);
                if(itr.first>ans){
                    ans = itr.first;
                    ni = itr.second;
                }
            }
            auto itr = seg.query(in[u],in[v]+1);
            if(itr.first>ans){
                ans = itr.first;
                ni = itr.second;
            }
            if(ans==-inf){
                cout<<-1<<endl;
                continue;
            }else{
                cout<<ans<<endl;
                seg.update(ni,make_pair(-inf,0));
                if(que[ni].size()){
                    ans = que[ni].top();
                    que[ni].pop();
                    seg.update(ni,make_pair(ans,ni));
                }
            }
        }
    }
}
0