Submission #1161698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161698		pinruei	Bridges (APIO19_bridges)	C++20	59 / 100	3100 ms	134908 KiB

bridges

#pragma region//         
#include<bits/stdc++.h>
#define int long long
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion
#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;

constexpr int mxn=5e4+1, mxm=1e5+1, blockSize=320;
int n, m, q, pa[mxn], sz[mxn];
si stck;
int ans[mxm];

void reset()
{
    iota(pa+1, pa+n+1, 1);
    //memset(sz, 1, sizeof(sz));
    fill(sz+1, sz+n+1, 1);
}


struct DSU
{
    int find(int x){return x==pa[x]?x:find(pa[x]);}
    void onion(int x, int y)
    {
        x=find(x), y=find(y);
        if(x==y) return; // already in the same set
        if(sz[x]>sz[y]) swap(x, y);
        stck.push(x);
        sz[y]+=sz[x];
        pa[x]=y;
    }
    void rollback(int x)
    {
        auto undo = [&]()
        {
            int t=stck.top();
            stck.pop();
            sz[pa[t]]-=sz[t]; // t is smaller than pa[t]
            pa[t]=t;    
        };
        while(stck.size()>x) undo();
    }
}dsu;

//cin..
int u[mxm], v[mxm], w[mxm], 
    q1[mxm], q2[mxm], q3[mxm];
    //t: 1->modify (1, edgeIdx, v), 2->query (2, node, w)

signed main()//         https://tioj.ck.tp.edu.tw/problems/2363
{   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    f21(i, m+1) cin>>u[i]>>v[i]>>w[i];
    cin>>q;
    f21(i, q+1) cin>>q1[i]>>q2[i]>>q3[i];
    vi toJoin[blockSize]; // store edges to join (mIdx)
    for(int l=1; l<q+1; l+=blockSize)
    {
        int r = min(q+1, l+blockSize); // range: [l, r)
        vi unchanged;//mIdx
        bs<mxm> changed;
        reset();
        vi ask;//qIdx
        auto cmp = [&](int a, int b){return q3[a]>q3[b];};
        //set<int, decltype(cmp)> ud(cmp);//qIdx
        vi ud;
        f3(i, l, r)
        {
            if(q1[i]==1) // modify
            {
                changed[q2[i]]=1;
                //ud.insert(i);
                ud.pb(i);
            }
            else ask.pb(i);
        }
        f3(i, l, r)
        {
            if(q1[i]==1) w[q2[i]]=q3[i];
            else
            {
                //cout << i <<"    ";
                toJoin[i-l].clear();
                for(int j : ud)
                {
                    if(w[q2[j]]<q3[i]) continue;;
                    toJoin[i-l].pb(q2[j]);
                    //cout<<w[q2[j]];
                }
                //cout << '\n';
            }
        }
        f21(i, m+1) if(!changed[i]) unchanged.pb(i);
        sort(begin(unchanged), end(unchanged),[&](int a, int b){return w[a]>w[b];}); 
        sort(begin(ask), end(ask), [&](int a, int b){return q3[a]>q3[b];});
        
        int unchangedPtr = 0;
        for(int i : ask)
        {
            for(; unchangedPtr<unchanged.size()&&w[unchanged[unchangedPtr]]>=q3[i]; unchangedPtr++)
                dsu.onion(u[unchanged[unchangedPtr]], v[unchanged[unchangedPtr]]);
            int preSize = stck.size();
            for(int j : toJoin[i-l]) dsu.onion(u[j], v[j]);
            ans[i] = sz[dsu.find(q2[i])];
            dsu.rollback(preSize);
        }
    }
    f21(i, q+1) if(q1[i]==2) cout<<ans[i]<<'\n';
    return 0;
}

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