제출 #1149927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149927		heeheeheehaaw	Bridges (APIO19_bridges)	C++20	13 / 100	3095 ms	5776 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 = 2;
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];
int visited[nmax], pl;
bool apare[nmax];
bool ex[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, adj[i].clear();
    }

    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 pl)
{
    int sum = dsu.siz[nod];
    visited[nod] = pl;
    for(auto it : adj[nod])
        if(visited[it] != pl)
            sum += dfs(it, pl);
    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)
                        ex[q[it].a] = true;
                    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;
                        if(u != v)
                        {
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }

                    }
                }

                for(auto it : aux)
                {
                    if(!ex[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;
                        if(u != v)
                        {
                            adj[u].push_back(v);
                            adj[v].push_back(u);
                        }
                    }
                }

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

                for(auto it : aux)
                {
                    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].clear();
                    adj[v].clear();
                    ex[q[it].a] = false;
                }
            }

            for(int j = stg; j <= i; j++)
                if(q[j].tip == 1)
                    aparemuc[q[j].a] = false, val[q[j].a] = q[j].b, ex[q[j].a] = false, apare[q[j].a] = false;
            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: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27