Submission #402713

#	Time	Username	Problem	Language	Result	Execution time	Memory
402713		thuanqvbn03	Bridges (APIO19_bridges)	C++17	100 / 100	2062 ms	9828 KiB

bridges

//Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int BLOCK = 400;

struct Edge
{
    int u, v, w;
};

struct Query
{
    int type, u, v, id;
};

struct DisjointSetWithRollback
{
    struct DisjointSetSave
    {
        int u, rankU, sizeConnectedU, v, rankV, sizeConnectedV;
        DisjointSetSave(int _u = 0, int _rankU = 0, int _sizeConnectedU = 0, int _v = 0, int _rankV = 0, int _sizeConnectedV = 0) : u(_u), rankU(_rankU), sizeConnectedU(_sizeConnectedU), v(_v), rankV(_rankV), sizeConnectedV(_sizeConnectedV) {}
    };
    int numNode;
    int parent[MAX_N], rank[MAX_N], sizeConnected[MAX_N];
    stack<DisjointSetSave> s;
    void init(int numNode)
    {
        this->numNode = numNode;
        for (int node = 1; node <= numNode; node++)
        {
            parent[node] = node;
            rank[node] = 0;
            sizeConnected[node] = 1;
        }
        while (s.size())
        {
            s.pop();
        }
    }
    int findRoot(int node) { return (node == parent[node] ? node : findRoot(parent[node])); }
    bool join(int u, int v)
    {
        u = findRoot(u);
        v = findRoot(v);
        if (u == v)
        {
            return false;
        }
        if (rank[u] < rank[v])
        {
            swap(u, v);
        }
        s.push(DisjointSetSave(u, rank[u], sizeConnected[u], v, rank[v], sizeConnected[v]));
        parent[v] = u;
        sizeConnected[u] += sizeConnected[v];
        if (rank[u] == rank[v])
        {
            rank[u]++;
        }
        return true;
    }
    void rollback()
    {
        if (s.empty())
        {
            return;
        }
        DisjointSetSave dsuSave = s.top();
        s.pop();
        parent[dsuSave.u] = dsuSave.u;
        rank[dsuSave.u] = dsuSave.rankU;
        sizeConnected[dsuSave.u] = dsuSave.sizeConnectedU;
        parent[dsuSave.v] = dsuSave.v;
        rank[dsuSave.v] = dsuSave.rankV;
        sizeConnected[dsuSave.v] = dsuSave.sizeConnectedV;
    }
    int getSizeConnected(int node)
    {
        return sizeConnected[findRoot(node)];
    }
} dsuRollback;

int numTest, numNode, numEdge, numQuery;
Edge edges[MAX_N];
int edgesId[MAX_N];
Query query[MAX_N], tmpQuery[BLOCK];
vector<pair<int, int>> change[MAX_N];
bool haveChange[MAX_N];
vector<int> edgesChange;
int answer[MAX_N];

void solve(int left, int right)
{
    edgesChange.clear();
    int cntQuery = 0;
    for (int i = left; i <= right; i++)
    {
        if (query[i].type == 2)
        {
            tmpQuery[++cntQuery] = query[i];
        }
        else
        {
            if (!haveChange[query[i].u])
            {
                haveChange[query[i].u] = true;
                edgesChange.push_back(query[i].u);
                change[query[i].u].push_back(make_pair(left - 1, edges[query[i].u].w));
            }
            change[query[i].u].push_back(make_pair(i, query[i].v));
        }
    }
    int cntEdge = 0;
    for (int i = 1; i <= numEdge; i++)
    {
        if (!haveChange[edgesId[i]])
        {
            edgesId[++cntEdge] = edgesId[i];
        }
    }
    sort(tmpQuery + 1, tmpQuery + cntQuery + 1, [&](const Query &a, const Query &b)
         { return a.v > b.v; });
    dsuRollback.init(numNode);
    int j = 1;
    for (int i = 1; i <= cntQuery; i++)
    {
        while (j <= cntEdge && edges[edgesId[j]].w >= tmpQuery[i].v)
        {
            dsuRollback.join(edges[edgesId[j]].u, edges[edgesId[j]].v);
            j++;
        }
        int cnt = 0;
        for (auto &id : edgesChange)
        {
            auto it = lower_bound(change[id].begin(), change[id].end(), make_pair(tmpQuery[i].id, 0));
            it--;
            if (it->second >= tmpQuery[i].v)
            {
                cnt += dsuRollback.join(edges[id].u, edges[id].v);
            }
        }
        answer[tmpQuery[i].id] = dsuRollback.getSizeConnected(tmpQuery[i].u);
        while (cnt--)
        {
            dsuRollback.rollback();
        }
    }
    for (auto &x : edgesChange)
    {
        edges[x].w = change[x].back().second;
        haveChange[x] = false;
        change[x].clear();
    }
    sort(edgesChange.begin(), edgesChange.end(), [&](const int &x, const int &y)
         { return edges[x].w > edges[y].w; });
    int pos = numEdge;
    while (edgesChange.size())
    {
        if (cntEdge == 0)
        {
            edgesId[pos--] = edgesChange.back();
            edgesChange.pop_back();
            continue;
        }
        if (edges[edgesChange.back()].w <= edges[edgesId[cntEdge]].w)
        {
            edgesId[pos--] = edgesChange.back();
            edgesChange.pop_back();
        }
        else
        {
            edgesId[pos--] = edgesId[cntEdge];
            cntEdge--;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
    {
        cin >> numNode >> numEdge;
        for (int i = 1; i <= numEdge; i++)
        {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
            edgesId[i] = i;
        }
        sort(edgesId + 1, edgesId + numEdge + 1, [&](const int &x, const int &y)
             { return edges[x].w > edges[y].w; });
        cin >> numQuery;
        for (int i = 1; i <= numQuery; i++)
        {
            cin >> query[i].type >> query[i].u >> query[i].v;
            query[i].id = i;
        }
        for (int i = 1; i <= numQuery; i += BLOCK)
        {
            solve(i, min(numQuery, i + BLOCK - 1));
        }
        for (int i = 1; i <= numQuery; i++)
        {
            if (query[i].type == 2)
            {
                cout << answer[i] << '\n';
            }
        }
    }
    return 0;
}

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