Submission #157975

#TimeUsernameProblemLanguageResultExecution timeMemory
157975combi1k1Bridges (APIO19_bridges)C++14
13 / 100
3072 ms16736 KiB
    #include<bits/stdc++.h>
     
    using namespace std;
     
    const int   N   = 1e5 + 5;
    const int   B   = 500;
     
    #define pb      push_back
    #define all(x)  x.begin(),x.end()
    #define sz(x)   x.size()
    #define X       first
    #define Y       second
     
    typedef pair<int,int>   ii;
    typedef pair<int,ii>    pii;
    typedef vector<pii>     vi;
     
    struct Edge {
        int x, y;
        int w, i;
        bool operator < (const Edge &a) const   {
            return  ii(w,i) > ii(a.w,a.i);
        }
    };
    struct Ques {
        int mas, ver, idx;
        bool operator < (const Ques& a) const   {
            return  mas > a.mas;
        }
    };
     
    bool uV[N], uE[N];
     
    namespace DSU   {
        int p[N], s[N];
        int lead(int x) {
            return  p[x] == x ? x : p[x] = lead(p[x]);
        }
        int join(int x,int y)   {
            x = lead(x);
            y = lead(y);
            if (x == y) return  0;
            if (uV[y])  swap(x,y);
            if (uV[x] == uV[y] && s[x] < s[y])
                swap(x,y);
            p[y] = x;
            s[x] += s[y];
            return  1;
        }
    };
     
    set<Edge>   E;
    int n, m;
    int x[N], y[N], w[N];
     
    void calc(vector<Ques>  qr) {
        iota(DSU::p + 1,DSU::p + 1 + n,1);
        fill(DSU::s + 1,DSU::s + 1 + n,1);
        fill(uV + 1,uV + 1 + n,0);
        fill(uE + 1,uE + 1 + m,0);
        vector<Ques>    sta;
        vector<int>     vx;
        vector<int>     ed;
        map<int,vi> mp;
        for(Ques t : qr)    {
            if(!t.idx)  uE[t.ver] = 1,  uV[x[t.ver]] = uV[y[t.ver]] = 1;
            else        sta.pb(t),      uV[t.ver] = 1;
        }
        for(int i = 1 ; i <= n ; ++i)   if (uV[i])  vx.pb(i);
        for(int i = 1 ; i <= m ; ++i)   if (uE[i])  ed.pb(i);
        sort(all(sta));
        auto it = E.begin();
        for(Ques t : sta)   {
            while (it != E.end() && (*it).w >= t.mas)   {
                if(!uE[(*it).i])    DSU::join((*it).x,(*it).y);
                it++;
            }
            for(int x : vx) mp[t.idx].pb(pii(x,{DSU::lead(x),DSU::s[DSU::p[x]]}));
        }
        for(Ques q : qr)    {
            if(!q.idx)  {
                Edge it = *E.find({x[q.ver],y[q.ver],w[q.ver],q.ver});
                E.erase(it);    it.w = w[q.ver] = q.mas;
                E.insert(it);   continue;
            }
            for(pii t : mp[q.idx])  DSU::p[t.X] = t.Y.X, DSU::s[t.X] = t.Y.Y;
            for(int i : ed) if (w[i] >= q.mas)
                DSU::join(x[i],y[i]);
            cout << DSU::s[DSU::lead(q.ver)] << "\n";
        }
    }
     
    int main()  {
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
     
        cin >> n >> m;
     
        for(int i = 1 ; i <= m ; ++i)    {
            cin >> x[i] >> y[i] >> w[i];
            E.insert({x[i],y[i],w[i],i});
        }
     
        int q;  cin >> q;
     
        vector<Ques>    v;
     
        for(int i = 1 ; i <= q ; ++i)   {
            int t, x, y;
            cin >> t >> x >> y;
            if (t == 1) v.pb({y,x,0});
            if (t == 2) v.pb({y,x,i});
        }
     
        for(int i = 0 ; i < q ; i += B)
            calc(vector<Ques>(v.begin() + i,v.begin() + min(q,i + B)));
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...