Submission #1251553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251553		hahahoang132	Bridges (APIO19_bridges)	C++20	100 / 100	1988 ms	11220 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
const ll inf = LLONG_MAX/5;
const ll mod = 1e9 + 7;
#define bit(x,y) ((x >> y) & 1LL)
ll p[N],sz[N];
struct haha
{
    ll x,y,w;
};
haha b[N];
struct query
{
    ll t,t1,t2;
};
query qr[N];
const ll bs = 800;
ll id[N],sus[N],last[N],ans[N];
ll cmp(ll x, ll y)
{
    return b[x].w < b[y].w;
}
stack<pair<ll,ll>> st;
ll fp(ll x)
{
    if(p[x] == 0) return x;
    else return fp(p[x]);
}
ll hop(ll x, ll y)
{
    ll px = fp(x);
    ll py = fp(y);
    if(px == py) return 0;
    if(sz[px] < sz[py]) swap(px,py);
    st.push({px,sz[px]});
    st.push({py,sz[py]});
    p[py] = px;
    sz[px] += sz[py];
    return 1;
}
void rb()
{
    ll id = st.top().first;
    ll osz = st.top().second;
    st.pop();
    p[id] = 0;
    sz[id] = osz;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin >> n >> m;
    ll i,j;
    for(i = 1;i <= m;i++)
    {
        id[i] = i;
        cin >> b[i].x >> b[i].y >> b[i].w;
        b[i].w = -b[i].w;
    }
    ll q;
    cin >> q;
    for(i = 1;i <= q;i++)
    {
        cin >> qr[i].t >> qr[i].t1 >> qr[i].t2;
        //if(qr[i].t == 2) swap(qr[i].t1,qr[i].t2);
    }
    for(i = 1;i <= q;i += bs)
    {
        sort(id + 1,id + 1 + m,cmp);
        ll l = i,r = min(i + bs - 1,q);
        for(j = 1;j <= m;j++)
        {
            sus[j] = 0;
            last[j] = 0;
        }
        while(!st.empty()) st.pop();
        for(j = 1;j <= n;j++)
        {
            p[j] = 0;
            sz[j] = 1;
        }
        vector<pair<ll,pair<ll,ll>>> a;
        vector<pair<pair<ll,ll>,pair<ll,ll>>> c;
        for(j = l;j <= r;j++)
        {
            if(qr[j].t == 1)
            {
                sus[qr[j].t1] = 1;
                c.push_back({{b[qr[j].t1].w,qr[j].t1},{last[qr[j].t1],j - 1}});
                b[qr[j].t1].w = -qr[j].t2;
                last[qr[j].t1] = j;
            }else
            {
                a.push_back({-qr[j].t2,{qr[j].t1,j}});
            }
        }
        for(j = 1;j <= m;j++)
        {
            if(last[j] > 0) c.push_back({{b[j].w,j},{last[j],q + 1}});
        }
        sort(a.begin(),a.end());
        sort(c.begin(),c.end());
        ll cur = 0;
        for(auto tmp : a)
        {
            ll w = tmp.first;
            ll pos = tmp.second.first;
            ll ti = tmp.second.second;
            while(cur + 1 <= m && (b[id[cur + 1]].w <= w || sus[id[cur + 1]]))
            {
                if(sus[id[cur + 1]])
                {
                    cur++;
                }else
                {
                    hop(b[id[cur + 1]].x,b[id[cur + 1]].y);
                    cur++;
                }
            }
            ll cnt = 0;
            for(auto tmp2 : c)
            {
                ll w2 = tmp2.first.first;
                ll idd = tmp2.first.second;
                ll lt = tmp2.second.first;
                ll rt = tmp2.second.second;
                if(lt <= ti && ti <= rt && w2 <= w)
                {
                    cnt += hop(b[idd].x,b[idd].y) * 2;
                }
            }
            ans[ti] = sz[fp(pos)];
            while(cnt--)
            {
                rb();
            }
        }
    }
    for(i = 1;i <= q;i++)
    {
        if(qr[i].t == 2) cout << ans[i] << "\n";
    }
}

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