oj.uz

Submission #969861

# Submission time Handle Problem Language Result Execution time Memory
969861 2024-04-25T17:37:08 Z JwFXoiz Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 9864 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 = 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;
            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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 37 ms 6636 KB Output is correct
4 Correct 32 ms 6492 KB Output is correct
5 Correct 110 ms 6824 KB Output is correct
6 Correct 61 ms 6848 KB Output is correct
7 Correct 396 ms 7488 KB Output is correct
8 Correct 151 ms 7132 KB Output is correct
9 Correct 505 ms 8656 KB Output is correct
10 Correct 96 ms 7216 KB Output is correct
11 Correct 164 ms 6872 KB Output is correct
12 Correct 97 ms 6868 KB Output is correct
13 Correct 170 ms 7180 KB Output is correct
14 Correct 120 ms 7060 KB Output is correct
15 Correct 225 ms 7092 KB Output is correct
16 Correct 495 ms 7904 KB Output is correct
17 Correct 192 ms 7680 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2213 ms 8528 KB Output is correct
2 Correct 2155 ms 8884 KB Output is correct
3 Correct 2274 ms 8876 KB Output is correct
4 Execution timed out 3045 ms 8852 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 3031 ms 9864 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 3014 ms 8188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2213 ms 8528 KB Output is correct
2 Correct 2155 ms 8884 KB Output is correct
3 Correct 2274 ms 8876 KB Output is correct
4 Execution timed out 3045 ms 8852 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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 37 ms 6636 KB Output is correct
4 Correct 32 ms 6492 KB Output is correct
5 Correct 110 ms 6824 KB Output is correct
6 Correct 61 ms 6848 KB Output is correct
7 Correct 396 ms 7488 KB Output is correct
8 Correct 151 ms 7132 KB Output is correct
9 Correct 505 ms 8656 KB Output is correct
10 Correct 96 ms 7216 KB Output is correct
11 Correct 164 ms 6872 KB Output is correct
12 Correct 97 ms 6868 KB Output is correct
13 Correct 170 ms 7180 KB Output is correct
14 Correct 120 ms 7060 KB Output is correct
15 Correct 225 ms 7092 KB Output is correct
16 Correct 495 ms 7904 KB Output is correct
17 Correct 192 ms 7680 KB Output is correct
18 Correct 2213 ms 8528 KB Output is correct
19 Correct 2155 ms 8884 KB Output is correct
20 Correct 2274 ms 8876 KB Output is correct
21 Execution timed out 3045 ms 8852 KB Time limit exceeded
22 Halted 0 ms 0 KB -