oj.uz

Submission #969858

# Submission time Handle Problem Language Result Execution time Memory
969858 2024-04-25T17:32:57 Z JwFXoiz Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 16640 KB 
#include <bits/stdc++.h>
 
using namespace std;

#define inf 0x3F3F3F3F
#define int long long

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 = 300;

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 8280 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 33 ms 8664 KB Output is correct
4 Correct 39 ms 8788 KB Output is correct
5 Correct 62 ms 9472 KB Output is correct
6 Correct 38 ms 8932 KB Output is correct
7 Correct 252 ms 10608 KB Output is correct
8 Correct 145 ms 9568 KB Output is correct
9 Correct 432 ms 14556 KB Output is correct
10 Correct 103 ms 9124 KB Output is correct
11 Correct 96 ms 9180 KB Output is correct
12 Correct 92 ms 9172 KB Output is correct
13 Correct 151 ms 9744 KB Output is correct
14 Correct 106 ms 9188 KB Output is correct
15 Correct 128 ms 9176 KB Output is correct
16 Correct 223 ms 9672 KB Output is correct
17 Correct 229 ms 9688 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3016 ms 14900 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 3024 ms 16640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 33 ms 8664 KB Output is correct
4 Correct 39 ms 8788 KB Output is correct
5 Correct 62 ms 9472 KB Output is correct
6 Correct 38 ms 8932 KB Output is correct
7 Correct 252 ms 10608 KB Output is correct
8 Correct 145 ms 9568 KB Output is correct
9 Correct 432 ms 14556 KB Output is correct
10 Correct 103 ms 9124 KB Output is correct
11 Correct 96 ms 9180 KB Output is correct
12 Correct 92 ms 9172 KB Output is correct
13 Correct 151 ms 9744 KB Output is correct
14 Correct 106 ms 9188 KB Output is correct
15 Correct 128 ms 9176 KB Output is correct
16 Correct 223 ms 9672 KB Output is correct
17 Correct 229 ms 9688 KB Output is correct
18 Execution timed out 3059 ms 15108 KB Time limit exceeded
19 Halted 0 ms 0 KB -