結果

問題 No.1054 Union add query
ユーザー yuto1115yuto1115
提出日時 2020-05-15 23:16:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,470 bytes
コンパイル時間 3,187 ms
コンパイル使用メモリ 217,212 KB
実行使用メモリ 64,780 KB
最終ジャッジ日時 2023-10-19 17:03:23
合計ジャッジ時間 6,866 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 262 ms
41,088 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

class unionfind {
    int n;
    vector<int> par;
public:
    unionfind(int n):n(n),par(n,-1) {}
    int root(int x) {
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void add() {
        n++;
        par.pb(-1);
    }
    bool same(int x,int y) { return root(x) == root(y); };
    bool merge(int x,int y) {
        x = root(x); y = root(y);
        if(x == y) return false;
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    int size(int x) { return -par[root(x)]; };
    bool connected() {
        rep(i,n-1) if(!same(i,i+1)) return false;
        return true;
    }
};

struct node {
    int par;
    vi ch;
};

template<typename T,typename MERGE,typename UPDATE>
class lazy_segtree {
    int n;
    vector<T> val,lazy;
    T identity_merge,identity_update;
    MERGE merge; // (T,T) -> T
    // update value for specified times
    UPDATE _update; // (T,T,int) -> T
    void eval(int k,int l,int r) {
        if(lazy[k] == identity_update) return;
        if(k < n-1) {
            lazy[k*2+1] = _update(lazy[k*2+1],lazy[k],1);
            lazy[k*2+2] = _update(lazy[k*2+2],lazy[k],1);
        }
        val[k] = _update(val[k],lazy[k],r-l);
        lazy[k] = identity_update;
    }

public:
    lazy_segtree(int _n,vector<T> init,T identity_merge,T identity_update,
                 MERGE merge,UPDATE update)
            :identity_merge(identity_merge),identity_update(identity_update),merge(merge),_update(update) {
        n = 1;
        while(n < _n) n *= 2;
        val = vector<T>(2*n-1,identity_merge);
        lazy = vector<T>(2*n-1,identity_update);
        rep(i,_n) val[i+n-1] = init[i];
        rrep(i,n-1) val[i] = merge(val[i*2+1],val[i*2+2]);
    }
    void update(int a,int b,T x,int k = 0,int l = 0,int r = -1) {
        if(r == -1) r = n;
        eval(k,l,r);
        if(a <= l && r <= b) {
            lazy[k] = _update(lazy[k],x,1);
            eval(k,l,r);
        } else if(a < r && l < b) {
            update(a,b,x,k*2+1,l,(l+r)/2);
            update(a,b,x,k*2+2,(l+r)/2,r);
            val[k] = merge(val[k*2+1],val[k*2+2]);
        }
    }
    // segment [a,b)
    T query(int a,int b,int k = 0,int l = 0,int r = -1) {
        if(r == -1) r = n;
        eval(k,l,r);
        if(b <= l || r <= a) return identity_merge;
        if(a <= l && r <= b) return val[k];
        T t1 = query(a,b,2*k+1,l,(l+r)/2);
        T t2 = query(a,b,2*k+2,(l+r)/2,r);
        return merge(t1,t2);
    }
    pair<T,T> operator[](int i) const { return make_pair(val[i],lazy[i]); }
};

int now = 0;

void dfs(int v,vector<node> &G,vi &in,vi &out) {
    in[v] = now++;
    for(int u : G[v].ch) {
        dfs(u,G,in,out);
    }
    out[v] = now;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vp que;
    unionfind uf(n);
    vector<node> G;
    rep(i,n) G.pb(node{-1,{}});
    int sz = n;
    rep(_,q) {
        int t,a,b;
        cin >> t >> a >> b;
        if(t == 1) {
            a--; b--;
            if(uf.same(a,b)) continue;
            int ra = uf.root(a),rb = uf.root(b);
            uf.add();
            G.pb(node{-1,{}});
            G[sz].ch.pb(ra);
            G[sz].ch.pb(rb);
            G[ra].par = sz;
            G[rb].par = sz;
            uf.merge(sz,ra);
            uf.merge(sz,rb);
            sz++;
        } else if(t == 2) {
            a--;
            int r = uf.root(a);
            que.eb(r,b);
        } else que.eb(a-1,-1);
    }
    G.pb(node{-1,{}});
    rep(i,sz) {
        if(G[i].par != -1) continue;
        G[i].par = sz;
        G[sz].ch.pb(i);
    }
    sz++;
    vi in(sz),out(sz);
    dfs(sz-1,G,in,out);
//    assert(now == sz);
    auto f = [](int a,int b){ return a+b; };
    auto g = [](int a,int b,int c){ return a+b*c; };
    lazy_segtree<int,decltype(f),decltype(g)> st(sz,vi(sz,0),0,0,f,g);
    for(auto [a,b] : que) {
        if(b == -1) {
            cout << st.query(in[a],in[a]+1) << "\n";
        } else {
            st.update(in[a],out[a],b);
        }
    }
//    rep(i,sz) {
//        cout << i << " " << G[i].par << "\n";
//        cout << "ch: ";
//        cout << G[i].ch;
//    }
//    rep(i,sz) cout << i << " in: " << in[i] << " out: " << out[i] << "\n";
}
0