結果

問題 No.2296 Union Path Query (Hard)
コンテスト
ユーザー momoyuu
提出日時 2023-05-05 23:23:22
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 4,361 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 7,076 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-23 12:20:48
合計ジャッジ時間 3,706 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct unionfind{
    int n;
    vector<int> parent;
    vector<int> num;

    unionfind(int n):n(n),parent(vector<int>(n)),num(vector<int>(n,1)){
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int n){
        if (parent[n] == n) return n;
        parent[n] = find(parent[n]);
        return parent[n];
    }

    int merge(int n,int m){
        n = find(n);
        m = find(m);
        if (n==m) return n;
        if (num[n]>num[m]) return merge(m,n);
        parent[m] = n;
        num[n] += num[m];
        return n;
    }

    int getnum(int n){
        return num[find(n)];
    }
};

ll d[2<<17],depth[2<<17];
ll par[2<<17][18];
ll pp[2<<17];
int n,x,q;
vector<pair<int,ll>> g[2<<17];
unionfind uf(2<<17);
vector<int> use;
pair<ll,ll> d1(int ni,int p,ll w){
    pair<ll,ll> now = make_pair(0ll,0ll);
    depth[ni] = depth[p] + w;
    d[ni] = d[p] + 1;
    par[ni][0] = p;
    for(int i = 1;i<=17;i++){
        par[ni][i] = par[ni][i-1];
        if(par[ni][i] == -1) continue;
        par[ni][i] = par[par[ni][i]][i-1];
    }

    for(auto&to:g[ni]) if(to.first!=p) {
        pair<ll,ll> nxt = d1(to.first,ni,to.second);
        now.first = max(now.first,max(nxt.first,nxt.second + now.second));
        now.second = max(nxt.second,now.second);
    }
    now.second += w;
    return now;

}
map<int,int> vis[2<<17];
int main(){
    vector<multiset<ll>>sum(2<<17);
    vector<map<ll,ll>>nnn(2<<17);
    vector<map<ll,ll>>mmm(2<<17);
    vector<ll> aa(2<<17,0);
    cin>>n>>x>>q;   
    for(int i = 0;i<n;i++){
        for(int j = 0;j<17;j++){
            par[i][j] = -1;
        }
    }
    for(int i = 0;i<n;i++) pp[i] = i;


    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int u;
            ll w;
            cin>>u>>w;
            int v = x;
            if(uf.getnum(u)<uf.getnum(v)) swap(u,v);
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
            pair<ll,ll> mx = d1(v,u,w);
            int kk = pp[uf.find(u)];
            uf.merge(u,v);
            pp[uf.find(u)] = kk;
            int pre = kk;
            int nu = u;
            if(pre==u){
                sum[pre].insert(mx.second);
                nnn[pre][v] = mx.second;
                aa[pre] = max(mx.first,mx.second);
                continue;
            }
            int now = 17;
            while(now){
                if(par[u][now]!=-1&&par[u][now]!=pre) u = par[u][now];
                now--;
            }
            assert(u!=pre);
            ll nxt = max(nnn[pre][u],depth[nu]+mx.second);
            if(vis[pre][u]++) sum[pre].erase(sum[pre].find(nnn[pre][u]));
            nxt = aa[pre];
            nxt = max(nxt,mx.first);
            if(sum[pre].size()){
                auto itr = sum[pre].end();
                itr--;
                nxt = max(nxt,*itr+mx.second+depth[nu]);
            }
            aa[pre] = nxt;
            sum[pre].insert(mx.second+depth[nu]);
            nnn[pre][u] = mx.second+depth[nu];
        }else if(op==2){
            int u,v;
            cin>>u>>v;
            int nu = u;
            int nv = v;
            if(uf.find(u)!=uf.find(v)){
                cout<<-1<<endl;
                continue;
            }
            if(u==v){
                cout<<0<<endl;
                continue;
            }
            if(d[u]>d[v]) swap(u,v);
            ll need = d[v] - d[u];
            int now = 0;
            while(need){
                if(need&1) v = par[v][now];
                now++;
                need >>= 1;
            }
            assert(d[u]==d[v]);
            now = 17;
            while(now){
                if(par[u][now]!=par[v][now]){
                    u = par[u][now];
                    v = par[v][now];
                }
                now--;
            }
            if(u!=v) u = par[u][0];
            ll ans = 2*depth[u] - depth[nu] - depth[nv];
            ans *= -1;
            cout<<ans<<endl;
            ans %= n;
            x += ans;
            x %= n;
        }else if(op==3){
            int u;
            cin>>u;
            int pre = pp[uf.find(u)];
            cout<<aa[pre]<<endl;

        }else{
            ll y;
            cin>>y;
            y %= n;
            x += y;
            x %= n;
        }
    }
}
0