結果

問題 No.1054 Union add query
ユーザー tarattata1tarattata1
提出日時 2020-05-15 22:50:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,647 bytes
コンパイル時間 1,318 ms
コンパイル使用メモリ 102,884 KB
実行使用メモリ 106,608 KB
最終ジャッジ日時 2024-09-19 12:07:37
合計ジャッジ時間 6,196 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 406 ms
52,040 KB
testcase_04 AC 792 ms
106,608 KB
testcase_05 WA -
testcase_06 AC 345 ms
75,316 KB
testcase_07 AC 279 ms
75,292 KB
testcase_08 AC 330 ms
75,344 KB
testcase_09 AC 630 ms
76,104 KB
testcase_10 AC 430 ms
76,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
//const long long MOD = 1000000007;
const long long MOD = 998244353;

using namespace std;

class UF
{
private:
    int         num;
    vector<int> par;
    vector<int> siz;
public:
    //vector<int> val;
public:
    UF(int n): num(n) {
        par.resize(n);
        siz.resize(n);
        //val.resize(n);
        int i;
        for(i=0; i<n; i++) {
            par[i]=i; siz[i]=1;
            //val[i]=0;
        }
    }
	
    int find(int x) {
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void unite(int x, int y) {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(siz[x]<siz[y]) {
            par[x]=y;
            siz[y]=siz[x]+siz[y];
            //val[y]=val[x]+val[y];
        }
        else {
            par[y]=x;
            siz[x]=siz[x]+siz[y];
            //val[x]=val[x]+val[y];
        }
    }

    bool same(int x, int y) {
        return find(x)==find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }

    int ngroup() {
    //int ngroup( int& ans ) {
        int count=0;
        int i;
        for(i=0; i<num; i++) {
            if(par[i]==i) {
                count++;
                //ans += (val[i]? siz[i]: siz[i]-1);
            }
        }
        return count;
    }
};

vector<vector<int> > g;
vector<int> eu, bf, af;

void dfs(int par, int curr)
{
    int cnt0=(int)eu.size();
    eu.push_back(curr);
    bf[curr] = cnt0;

    int i;
    for (i = 0; i < (int)g[curr].size(); i++) {
        int next = g[curr][i];
        if (par == next) continue;

        dfs(curr, next);
    }
    af[curr] = (int)eu.size();

    return;
}

const long long INF2 = (((ll)1<<31)-1);

template<class T> class SegTree   // 0-indexed
{
private:
    int n;             // 葉の数
    vector<T> data;    // ノードの値を持つ配列
    vector<T> lazy;    // 遅延評価を持つ配列

    T def;                // 初期値かつ単位元
    
    T operation(T a, T b)    // 区間クエリで使う処理
    {
        //return min(a, b);   // 区間minクエリ
        return a+b;           // 区間和クエリ
    }

    T update(T a, T b)      // 点更新で使う処理
    {
        //return a+b;   // 加算の場合
        return b;       // 更新の場合
    }

    void eval( int k, int l, int r )   // ノードkについて遅延評価を行う
    {
        if(lazy[k] != 0) {
            data[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
        return;
    }

    void _add(int a, int b, T x, int k, int l, int r) {
        if(r < 0) r = n;
        eval(k, l, r);   // k 番目のノードに対して遅延評価を行う
        
        if(b <= l || r <= a) return;   // 範囲外なら何もしない
    
        // 完全に被覆しているならば、遅延配列に値を入れた後に評価
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }

        // そうでないならば、子ノードの値を再帰的に計算して、
        // 計算済みの値をもらってくる
        else {
            _add(a, b, x, 2*k+1, l, (l+r)/2);
            _add(a, b, x, 2*k+2, (l+r)/2, r);
            data[k] = data[2*k+1] + data[2*k+2];
        }
    }

    // 区間[a,b)の総和。ノードk=[l,r)に着目している。
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def; // 交差しない

        eval(k, l, r);
        if (a <= l && r <= b)
            return data[k]; // a,l,r,bの順で完全に含まれる
        else {
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
            return operation(c1, c2);
        }
    }
 
public:
    SegTree(int _n) {     // _n:必要サイズ
        //def = INF2;        // 初期値かつ単位元（minのときINF2)
        def = 0;             // 初期値かつ単位元（和のとき0)
        n = 1;
        while (n < _n) n *= 2;
        data = vector<T>(2 * n - 1, def);
        lazy = vector<T>(2 * n - 1, 0);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    // 区間更新
    void add(int a, int b, T x) {
        return _add(a, b, x, 0, 0, n);
    }

    // [a, b)の区間クエリを実行
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }
 
    // 添字でアクセス
    T operator[](int i) {
        return data[i + n - 1];
    }
};

void solve()
{
    int n, Q;
    scanf("%d%d", &n, &Q);
    vector<int> t(Q), a(Q), b(Q);
    int cnt = 0;
    int i;
    for (i = 0; i < Q; i++) {
        scanf("%d%d%d", &t[i], &a[i], &b[i]); a[i]--;
        if(t[i]==1) b[i]--;
        if (t[i] == 1) {
            cnt++;
        }
    }
    int num = cnt;

    vector<int> mp(n+num);
    for (i = 0; i < n + num; i++) mp[i] = i;

    UF uf(n + num);
    g.resize(n + num);
    bf.resize(n + num);
    af.resize(n + num);
    cnt = 0;
    for (i = 0; i < Q; i++) {
        if (t[i] == 1) {
            int aa = mp[uf.find(a[i])];
            int bb = mp[uf.find(b[i])];
            int id = n + cnt;
            g[id].push_back(aa);
            g[aa].push_back(id);
            g[id].push_back(bb);
            g[bb].push_back(id);
            if (uf.same(aa, bb)) {
                cnt++;
                continue;
            }
            uf.unite(aa, bb);
            uf.unite(aa, id);
            int p = uf.find(aa);
            mp[p] = id;
            cnt++;
        }
    }
    set<int> ss;
    for (i = 0; i < n; i++) {
        ss.insert(mp[uf.find(i)]);
    }
    auto it0 = ss.begin();
    for (; it0 != ss.end(); ++it0) {
        dfs(-1, *it0);
    }

    SegTree<ll> S(n + num);
    UF uf2(n + num);
    for (i = 0; i < n + num; i++) mp[i] = i;
    cnt = 0;
    for (i = 0; i < Q; i++) {
        if (t[i] == 1) {
            int aa = mp[uf2.find(a[i])];
            int bb = mp[uf2.find(b[i])];
            int id = n + cnt;
            if (uf2.same(aa, bb)) {
                cnt++;
                continue;
            }
            uf2.unite(aa, bb);
            uf2.unite(aa, id);
            int p = uf2.find(aa);
            mp[p] = id;
            cnt++;
        }
        else if (t[i] == 2) {
            int aa = mp[uf2.find(a[i])];
            int t0 = bf[aa], t1 = af[aa];
            S.add(t0, t1, b[i]);
        }
        else {
            int aa = bf[a[i]];
            ll ans=S.query(aa, aa+1);
            printf("%lld\n", ans);
        }
    }


    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}
0