Submission #1260288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260288		khanhdangiuu	Bridges (APIO19_bridges)	C++20	13 / 100	3100 ms	69468 KiB

bridges

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pi 3.14159265358979323846 
#define pb push_back
#define ar array

template<typename T, typename cmp = std::greater<T>>
using pq = priority_queue<T, vector<T>, cmp>;

template<typename T, typename cmp = std::less<T>>
using ordered_set = tree<T, __gnu_pbds::null_type, cmp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

void chay()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define task "Hi"
    freopen(task".INP", "r", stdin);
    freopen(task".OUT", "w", stdout);
}

const int N = 2e5, INF = numeric_limits<int>::max();
const int block = 600;
const long long INFLL = numeric_limits<ll>::max();
long long M = 1e9+7;


struct Edge 
{
    int u, v, w, id;
    Edge(int _u = 0, int _v = 0, int _w = 0, int _id = 0) 
    {
        u = _u;
        v = _v;
        w = _w;
        id = _id;
    }
};


struct DRB 
{
    int loai;
    Edge canh;

    DRB(int _loai = 0, Edge _canh = Edge()) : loai(_loai), canh(_canh) {}
};


struct DSURollBack
{
    vector<vector<int>> rollback;
    vector<vector<Edge>> cay;
    vector<int> pa, sz;
    map<ll,int> m;
    int n, idn, mtime;

    ll id(const int &a, const int &b)
    {
        return 1ll * a * idn + b;
    }

    ll id(const ar<int,2> &a)
    {
        return 1ll * a[0] * idn + a[1];
    }

    ar<int,2> dao(ll id)
    {
        return {id/idn, id%idn};
    }

    int timpa(int u)
    {
        if (u == pa[u]) return u;
        return timpa(pa[u]);
    }

    bool hop(int id, int x, int y)
    {
        x = timpa(x);
        y = timpa(y);
        if (x == y) return false;

        if (sz[x] > sz[y])
        {
            swap(x, y);
        }
        rollback[id].pb(x);
        sz[y] += sz[x];
        pa[x] = y;

        return true;
    }

    void update(int u, int v, Edge canh, int id, int l, int r)
    {
        if (r < u || l > v) return;
        if (u <= l && r <= v)
        {
            cay[id].pb(canh);
            return;
        }
        int m = (l+r)>>1;
        update(u, v, canh, id<<1, l, m);
        update(u, v, canh, id<<1|1, m+1, r);
    }

    void update(int dau, int cuoi, Edge canh)
    {
        update(dau, cuoi, canh, 1, 1, mtime);
    }

    int kq, dinh, trongluong;

    void tinh(int vt, int id, int l, int r)
    {
        if (r < vt || l > vt) return;
        for (Edge canh : cay[id])
        {
            if (canh.w >= trongluong)
            {
                hop(id, canh.u, canh.v);
                //cout<<"Merge: "<<canh.id<<' '<<canh.u<<' '<<canh.v<<' '<<canh.w<<'\n';
            }
        }

        if (l == r)
        {
            kq = sz[timpa(dinh)];
        }
        else
        {
            int m = (l+r)>>1;
            tinh(vt, id<<1, l, m);
            tinh(vt, id<<1|1, m+1, r);
        }


        while (!rollback[id].empty())
        {
            int node = rollback[id].back();
            rollback[id].pop_back();
            sz[pa[node]] -= sz[node];
            pa[node] = node;
        }
    }

    int lay(int vt, int _dinh, int _trongluong)
    {
        dinh = _dinh;
        trongluong = _trongluong;
        kq = 0;
        tinh(vt, 1, 1, mtime);
        return kq;
    }

    void theocanh(int _n, vector<DRB> &v, int _mtime = -1)
    {
        m.clear();
        this->n = _n;
        this->idn = n+1;
        this->mtime = v.size()-1;
        if (_mtime != -1) mtime = _mtime;
        
        pa.resize(n+1);
        sz.resize(n+1);
        for (int i = 1; i <= n; i++) 
        {
            pa[i] = i;
            sz[i] = 1;
        }
        rollback.assign(4*mtime+5,{});
        cay.assign(4*mtime+5,{});

        for (int i = 1; i < v.size(); i++)
        {
            int loai = v[i].loai;
            Edge canh = v[i].canh;
            if (loai == 0) continue;
            if (canh.u > canh.v) swap(canh.u, canh.v);

            ll d = id(canh.u, canh.v);
            if (loai == 1) 
            {
                int e = m[d];
                if (!e) // Them
                { 
                    m[d] = i; 
                }
                else // Thay
                {
                    update(e, i-1, v[e].canh);
                    //cout<<e<<' '<<i-1<<' '<<v[e].canh.u<<' '<<v[e].canh.v<<' '<<v[e].canh.w<<'\n';
                    m[d] = i;
                }
            }
            else if (loai == 2)
            {
                if (!m.count(d)) continue; // khong ton tai
                int e = m[d];
                update(e, i-1, canh);
                m.erase(d);
            }       
        }

        for (auto [x, dau] : m)
        {
            Edge canh = v[dau].canh;
            update(dau, mtime, canh);
            //cout<<dau<<' '<<mtime<<' '<<canh.u<<' '<<canh.v<<' '<<canh.w<<'\n';
        }
    }
    
    void theoid(int _n, vector<DRB> &v, int _mtime = -1)
    {
        m.clear();
        this->n = _n;
        this->idn = n+1;
        this->mtime = v.size()-1;
        if (_mtime != -1) mtime = _mtime;
        
        pa.resize(n+1);
        sz.resize(n+1);
        for (int i = 1; i <= n; i++) 
        {
            pa[i] = i;
            sz[i] = 1;
        }
        rollback.assign(4*mtime+5,{});
        cay.assign(4*mtime+5,{});

        for (int i = 1; i < v.size(); i++)
        {
            int loai = v[i].loai;
            Edge canh = v[i].canh;
            if (loai == 0) continue;
            if (canh.u > canh.v) swap(canh.u, canh.v);

            ll d = canh.id;
            if (loai == 1) 
            {
                int e = m[d];
                if (!e) // Them
                { 
                    m[d] = i; 
                }
                else // Thay
                {
                    update(e, i-1, v[e].canh);
                    //cout<<e<<' '<<i-1<<':'<<v[e].canh.id<<' '<<v[e].canh.u<<' '<<v[e].canh.v<<' '<<v[e].canh.w<<'\n';
                    m[d] = i;
                }
            }
            else if (loai == 2)
            {
                if (!m.count(d)) continue; // khong ton tai
                int e = m[d];
                update(e, i-1, canh);
                m.erase(d);
            }       
        }

        for (auto [x, dau] : m)
        {
            Edge canh = v[dau].canh;
            update(dau, mtime, canh);
            //cout<<dau<<' '<<mtime<<':'<<canh.id<<' '<<canh.u<<' '<<canh.v<<' '<<canh.w<<'\n';
        }
    }
};

int n, m, q;

void solve()
{
    vector<DRB> tt = {DRB()};
    cin>>n>>m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin>>u>>v>>w;
        tt.pb(DRB(1, Edge(u, v, w, i)));
    }
    vector<ar<int,3>> qu;
    cin>>q;
    while (q--)
    {
        int e;
        cin>>e;
        if (e == 1)
        {
            int i, w;
            cin>>i>>w;
            Edge d = tt[i].canh; d.w = w;
            tt.pb(DRB(1, d));
        }
        else
        {
            int v, w;
            cin>>v>>w;
            qu.pb({int(tt.size()), v, w});
            tt.pb(DRB(0, Edge()));
        }
    }
    
    DSURollBack a;
    a.theoid(n, tt);
    
    for (ar<int,3> x : qu)
    {
        cout<<a.lay(x[0], x[1], x[2])<<'\n';
    }
}
 
signed main ()
{
    //chay();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;   
    //cin>>t; 
    while (t--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'std::array<int, 2> DSURollBack::dao(long long int)':
bridges.cpp:75:19: warning: narrowing conversion of '(id / ((long long int)((DSURollBack*)this)->DSURollBack::idn))' from 'long long int' to 'int' [-Wnarrowing]
   75 |         return {id/idn, id%idn};
      |                 ~~^~~~
bridges.cpp:75:27: warning: narrowing conversion of '(id % ((long long int)((DSURollBack*)this)->DSURollBack::idn))' from 'long long int' to 'int' [-Wnarrowing]
   75 |         return {id/idn, id%idn};
      |                         ~~^~~~
bridges.cpp: In function 'void chay()':
bridges.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(task".INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen(task".OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27