oj.uz

Submission #969859

# Submission time Handle Problem Language Result Execution time Memory
969859 2024-04-25T17:34:03 Z JwFXoiz Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 12068 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 = 400;

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;

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]--;
    }
    for (int l = 0; l < Q; l += B)
    {
        dsu.init(n);
        int r = min(Q, l + B);
        for (int i = l; i < r; i++) if (q[i][0] == 1) inq[q[i][1]] = 1;
        vector<int> o, oe(m);
        iota(oe.begin(), oe.end(), 0);
        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 34 ms 6636 KB Output is correct
4 Correct 31 ms 6496 KB Output is correct
5 Correct 61 ms 6760 KB Output is correct
6 Correct 63 ms 6736 KB Output is correct
7 Correct 425 ms 7704 KB Output is correct
8 Correct 111 ms 7128 KB Output is correct
9 Correct 390 ms 8736 KB Output is correct
10 Correct 89 ms 6872 KB Output is correct
11 Correct 75 ms 6868 KB Output is correct
12 Correct 77 ms 6936 KB Output is correct
13 Correct 154 ms 7208 KB Output is correct
14 Correct 98 ms 7124 KB Output is correct
15 Correct 97 ms 7128 KB Output is correct
16 Correct 283 ms 7956 KB Output is correct
17 Correct 160 ms 7128 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2775 ms 8876 KB Output is correct
2 Correct 2708 ms 11488 KB Output is correct
3 Correct 2645 ms 11484 KB Output is correct
4 Execution timed out 3097 ms 12068 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 3095 ms 9588 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 3045 ms 7796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2775 ms 8876 KB Output is correct
2 Correct 2708 ms 11488 KB Output is correct
3 Correct 2645 ms 11484 KB Output is correct
4 Execution timed out 3097 ms 12068 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 34 ms 6636 KB Output is correct
4 Correct 31 ms 6496 KB Output is correct
5 Correct 61 ms 6760 KB Output is correct
6 Correct 63 ms 6736 KB Output is correct
7 Correct 425 ms 7704 KB Output is correct
8 Correct 111 ms 7128 KB Output is correct
9 Correct 390 ms 8736 KB Output is correct
10 Correct 89 ms 6872 KB Output is correct
11 Correct 75 ms 6868 KB Output is correct
12 Correct 77 ms 6936 KB Output is correct
13 Correct 154 ms 7208 KB Output is correct
14 Correct 98 ms 7124 KB Output is correct
15 Correct 97 ms 7128 KB Output is correct
16 Correct 283 ms 7956 KB Output is correct
17 Correct 160 ms 7128 KB Output is correct
18 Correct 2775 ms 8876 KB Output is correct
19 Correct 2708 ms 11488 KB Output is correct
20 Correct 2645 ms 11484 KB Output is correct
21 Execution timed out 3097 ms 12068 KB Time limit exceeded
22 Halted 0 ms 0 KB -