Submission #1149917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149917		heeheeheehaaw	Bridges (APIO19_bridges)	C++20	14 / 100	576 ms	11332 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

struct muchie
{
    int a, b, id;
};

struct query
{
    int tip, a, b, rez;
};

const int bsiz = 1000;
const int nmax = 100005;
muchie muc[nmax];
int val[nmax];
pair<int, int> mc[nmax];
bool aparemuc[nmax];
vector<int> adj[nmax];
query q[nmax];
bool visited[nmax];
bool apare[nmax];

struct DSU
{
    vector<int> parent, siz;
    void init(int n)
    {
        parent.resize(n + 1);
        siz.resize(n + 1);
        for(int i = 1; i <= n; i++)
            siz[i] = 1, parent[i] = i;
    }

    int cauta(int u)
    {
        if(u == parent[u])
            return u;
        return parent[u] = cauta(parent[u]);
    }

    void unite(int u, int v)
    {
        u = cauta(u);
        v = cauta(v);
        if(u == v)
            return;
        if(siz[u] > v)
            swap(u, v);
        parent[u] = v;
        siz[v] += siz[u];
        return;
    }
};

DSU dsu;

int dfs(int nod)
{
    int sum = dsu.siz[nod];
    visited[nod] = true;
    for(auto it : adj[nod])
        if(visited[it] == false)
            sum += dfs(it);
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m, k;
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        muc[i] = {a, b, i};
        val[i] = c;
        mc[i] = {a, b};
    }

    cin>>k;
    int cntbuc = 1, stg = 1;
    for(int i = 1; i <= k; i++)
    {
        cin>>q[i].tip>>q[i].a>>q[i].b;
        if(i % bsiz == 0 || i == k)
        {
            dsu.init(n);
            vector<int> qq;
            vector<int> aux;
            for(int j = i; j >= stg; j--)
                if(q[j].tip == 1)
                {
                    aparemuc[q[j].a] = true;
                    aux.push_back(j);
                }
                else
                {
                    qq.push_back(j);
                }

            sort(qq.begin(), qq.end(), [](int a, int b)
            {
                return q[a].b > q[b].b;
            });
            sort(muc + 1, muc + m + 1, [](muchie a, muchie b)
            {
                return val[a.id] > val[b.id];
            });

            int st = 1;
            for(auto j : qq)
            {
                while(st <= m && (val[muc[st].id] >= q[j].b || aparemuc[muc[st].id]))
                {
                    if(!aparemuc[muc[st].id])
                        dsu.unite(muc[st].a, muc[st].b);
                    st++;
                }

                int rez = 0;
                for(auto it : aux)
                {
                    if(it < j && !apare[q[it].a] && q[it].b >= q[j].b)
                    {
                        int u = dsu.cauta(mc[q[it].a].first);
                        int v = dsu.cauta(mc[q[it].a].second);
                        apare[q[it].a] = true;
                        adj[u].push_back(v);
                        adj[v].push_back(u);
                    }
                }

                for(auto it : aux)
                {
                    if(it > j && !apare[q[it].a] && val[q[it].a] >= q[j].b)
                    {
                        int u = dsu.cauta(mc[q[it].a].first);
                        int v = dsu.cauta(mc[q[it].a].second);
                        apare[q[it].a] = true;
                        adj[u].push_back(v);
                        adj[v].push_back(u);

                    }
                }

                q[j].rez = dfs(dsu.cauta(q[j].a));

                for(auto it : aux)
                {
                    if(apare[q[it].a])
                    {
                        int u = dsu.cauta(mc[q[it].a].first);
                        int v = dsu.cauta(mc[q[it].a].second);
                        apare[q[it].a] = false;
                        adj[u].pop_back();
                        adj[v].pop_back();
                        visited[u] = visited[v] = false;
                    }
                }
            }

            for(int j = i; j >= stg; j--)
                if(q[j].tip == 1)
                    aparemuc[q[j].a] = false, val[q[j].a] = q[j].b;
            cntbuc++;
            stg = i + 1;
        }
    }

    for(int i = 1; i <= k; i++)
        if(q[i].tip == 2)
            cout<<q[i].rez<<'\n';
    return 0;
}

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