oj.uz

Submission #969862

# Submission time Handle Problem Language Result Execution time Memory
969862 2024-04-25T17:37:40 Z JwFXoiz Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 8816 KB 
#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 = 230;

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;
            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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 25 ms 6652 KB Output is correct
4 Correct 30 ms 6492 KB Output is correct
5 Correct 33 ms 6692 KB Output is correct
6 Correct 23 ms 6492 KB Output is correct
7 Correct 165 ms 7716 KB Output is correct
8 Correct 91 ms 7064 KB Output is correct
9 Correct 310 ms 7632 KB Output is correct
10 Correct 73 ms 6868 KB Output is correct
11 Correct 63 ms 6844 KB Output is correct
12 Correct 107 ms 7040 KB Output is correct
13 Correct 92 ms 6872 KB Output is correct
14 Correct 68 ms 6828 KB Output is correct
15 Correct 72 ms 6812 KB Output is correct
16 Correct 163 ms 7652 KB Output is correct
17 Correct 125 ms 7120 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2794 ms 8640 KB Output is correct
2 Correct 2923 ms 8744 KB Output is correct
3 Correct 2729 ms 8700 KB Output is correct
4 Execution timed out 3100 ms 8816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 8768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 7948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2794 ms 8640 KB Output is correct
2 Correct 2923 ms 8744 KB Output is correct
3 Correct 2729 ms 8700 KB Output is correct
4 Execution timed out 3100 ms 8816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 25 ms 6652 KB Output is correct
4 Correct 30 ms 6492 KB Output is correct
5 Correct 33 ms 6692 KB Output is correct
6 Correct 23 ms 6492 KB Output is correct
7 Correct 165 ms 7716 KB Output is correct
8 Correct 91 ms 7064 KB Output is correct
9 Correct 310 ms 7632 KB Output is correct
10 Correct 73 ms 6868 KB Output is correct
11 Correct 63 ms 6844 KB Output is correct
12 Correct 107 ms 7040 KB Output is correct
13 Correct 92 ms 6872 KB Output is correct
14 Correct 68 ms 6828 KB Output is correct
15 Correct 72 ms 6812 KB Output is correct
16 Correct 163 ms 7652 KB Output is correct
17 Correct 125 ms 7120 KB Output is correct
18 Correct 2794 ms 8640 KB Output is correct
19 Correct 2923 ms 8744 KB Output is correct
20 Correct 2729 ms 8700 KB Output is correct
21 Execution timed out 3100 ms 8816 KB Time limit exceeded
22 Halted 0 ms 0 KB -