Submission #987285

#	Time	Username	Problem	Language	Result	Execution time	Memory
987285		aykhn	Bridges (APIO19_bridges)	C++17	100 / 100	1988 ms	13076 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
 
#define inf 0x3F3F3F3F
 
struct DSU
{
    int n;
    vector<int> e;
    void init(int N)
    {
        n = N;
        e.assign(n + 1, -1);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    void unite(int x, int y)
    {
        x = get(x), y = get(y);
        if (x == y) return;
        if (e[x] > e[y]) swap(x, y); 
        e[x] += e[y];
        e[y] = x;
    }
};
 
const int MXN = 1e5 + 5;
const int B = 500;
 
int n, m, Q;
vector<int> adj[MXN];
array<int, 3> e[MXN];
array<int, 3> q[MXN];
DSU dsu;
int inq[MXN], renw[MXN], used[MXN], ans[MXN];
int res;
vector<int> node, o, oe;
 
void dfs(int a)
{
    node.push_back(a);
    res += -dsu.e[dsu.get(a)];
    used[a] = 1;
    for (int v : adj[a])
    {
        if (!used[v]) dfs(v);
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) for (int j = 0; j < 3; j++) cin >> e[i][j];
    cin >> Q;
    for (int i = 0; i < Q; i++) 
    {
        for (int j = 0; j < 3; j++) cin >> q[i][j];
        q[i][1]--;
    }
    oe.assign(m, 0);
    iota(oe.begin(), oe.end(), 0);
    for (int l = 0; l < Q; l += B)
    {
        dsu.init(n);
        o.clear();
        int r = min(Q, l + B);
        for (int i = l; i < r; i++) if (q[i][0] == 1) inq[q[i][1]] = 1;
        for (int i = l; i < r; i++) if (q[i][0] == 2) o.push_back(i);
        sort(oe.begin(), oe.end(), [&](int a, int b)
        {
            return e[a][2] > e[b][2];
        });
        sort(o.begin(), o.end(), [&](int a, int b)
        {
            return q[a][2] > q[b][2];
        });
        int j = 0;
        for (int x : o)
        {
            while (j < m && e[oe[j]][2] >= q[x][2]) 
            {
                if (!inq[oe[j]]) dsu.unite(e[oe[j]][0], e[oe[j]][1]);
                j++;
            }
            for (int i = x - 1; i >= l; i--)
            {
                if (q[i][0] == 1 && !renw[q[i][1]])
                {
                    renw[q[i][1]] = 1;
                    if (q[i][2] >= q[x][2]) adj[dsu.get(e[q[i][1]][0])].push_back(dsu.get(e[q[i][1]][1])), adj[dsu.get(e[q[i][1]][1])].push_back(dsu.get(e[q[i][1]][0]));
                }
            }
            for (int i = x + 1; i < r; i++)
            {
                if (q[i][0] == 1 && !renw[q[i][1]])
                {
                    renw[q[i][1]] = 1;
                    if (e[q[i][1]][2] >= q[x][2]) adj[dsu.get(e[q[i][1]][0])].push_back(dsu.get(e[q[i][1]][1])), adj[dsu.get(e[q[i][1]][1])].push_back(dsu.get(e[q[i][1]][0]));
                }
            }
            res = 0;
            dfs(dsu.get(q[x][1] + 1));
            for (int x : node) used[x] = 0;
            node.clear();
            ans[x] = res;
            for (int i = l; i < r; i++) 
            {
                if (q[i][0] == 1) 
                {
                    renw[q[i][1]] = 0;
                    adj[dsu.get(e[q[i][1]][0])].clear(), adj[dsu.get(e[q[i][1]][1])].clear();
                }
            }
        }
        for (int i = l; i < r; i++)
        {
            if (q[i][0] == 1) e[q[i][1]][2] = q[i][2], inq[q[i][1]] = 0;
        }
    }
    for (int i = 0; i < Q; i++) if (q[i][0] == 2) cout << ans[i] << ' ';
    cout << '\n';
}

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