Submission #1322604

#TimeUsernameProblemLanguageResultExecution timeMemory
1322604NValchanovBridges (APIO19_bridges)C++20
13 / 100
3095 ms67200 KiB
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;
const int MAXQ = 1e5 + 10;
const int BLOCK = 320;

struct DSU
{
    int leader[MAXN];
    int sz[MAXN];
    stack < int > st;

    DSU(){};

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            leader[i] = i;
            sz[i] = 1;
        }
    }

    int findLeader(int u)
    {
        return leader[u] == u ? u : findLeader(leader[u]);
    }

    bool connected(int u, int v)
    {
        return findLeader(u) == findLeader(v);
    }

    void unite(int u, int v)
    {
        if(connected(u, v))
            return;

        u = findLeader(u);
        v = findLeader(v);

        if(sz[u] < sz[v])
            swap(u, v);

        sz[u] += sz[v];
        leader[v] = u;

        st.push(v);
    }

    void rollback(int t)
    {
        while(st.size() > t)
        {
            int u = st.top();
            st.pop();

            sz[leader[u]] -= sz[u];
            leader[u] = u;
        }
    }

    int edges()
    {
        return (int)st.size();
    }

    int query(int u)
    {
        return sz[findLeader(u)];
    }
};

int n, m, q;
DSU dsu;
bool used[MAXM];
int u[MAXM], v[MAXM], w[MAXM];
int type[MAXQ], x[MAXQ], y[MAXQ]; 
int ans[MAXN];

vector < int > inc[BLOCK];

bool cmp_edges(int i, int j)
{
    return w[i] > w[j];
}

bool cmp_queries(int i, int j)
{
    return y[i] > y[j];
}

void read()
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
    }

    cin >> q;

    for(int i = 0; i < q; i++)
    {
        cin >> type[i] >> x[i] >> y[i];
    }
}

void solve()
{
    for(int l = 0; l < q; l += BLOCK)
    {
        int r = min(l + BLOCK - 1, q - 1);

        for(int i = 1; i <= m; i++)
        {
            used[i] = false;
        }

        vector < int > updates;
        vector < int > calc;

        vector < int > unchanged;

        for(int i = l; i <= r; i++)
        {
            if(type[i] == 1)
            {
                used[x[i]] = true;
                updates.push_back(i);
            }
            else
            {
                calc.push_back(i);
            }
        }

        for(int i = 1; i <= m; i++)
        {
            if(!used[i])
                unchanged.push_back(i);
        }

        for(int i = 0; i < BLOCK; i++)
        {
            inc[i].clear();
        }

        for(int i = l; i <= r; i++)
        {
            if(type[i] == 1)
            {
                w[x[i]] = y[i];
            }
            else
            {
                for(int &idx : updates)
                {
                    if(w[x[idx]] >= y[i])
                    {
                        inc[i - l].push_back(x[idx]);
                    }
                }
            }
        }

        sort(unchanged.begin(), unchanged.end(), cmp_edges);
        sort(calc.begin(), calc.end(), cmp_queries);

        dsu.init(n);

        int ptr = 0;
        int sz = unchanged.size();

        for(int &idx : calc)
        {
            while(ptr < sz && w[unchanged[ptr]] >= y[idx])
            {
                dsu.unite(u[unchanged[ptr]], v[unchanged[ptr]]);
                ptr++;
            }

            int t = dsu.edges();

            for(int &idx : inc[idx - l])
            {
                dsu.unite(u[idx], v[idx]);
            }

            ans[idx] = dsu.query(x[idx]);

            dsu.rollback(t);
        }
    }

    for(int i = 0; i < q; i++)
    {
        if(ans[i] != 0)
        {
            cout << ans[i] << endl;
        }
    }
}

int main()
{
    read();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...