oj.uz

Submission #591715

# Submission time Handle Problem Language Result Execution time Memory
591715 2022-07-07T19:23:33 Z piOOE Bridges (APIO19_bridges) C++17
100 / 100
 2387 ms 14244 KB 
//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 50002, M = 100001, B = 500, Q = 100001;
const int mod = 998244353;
const ld eps = 1e-9;

int p[N], sz[N];

void init(int n) {
    fill(sz, sz + n, 1);
    iota(p, p + n, 0);
}

int get(int a) {
    return (a == p[a] ? a : p[a] = get(p[a]));
}

void mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

bool used[N], nww[M];
vector<pair<int, int>> g[N];
int now = 0, wnow, U[M], V[M], W[M], prv[M + Q], nxt[M + Q], tp[Q], x[Q], y[Q], ans[Q], prvv[Q];

vector<int> vis;

void dfs(int v) {
    vis.push_back(v);
    used[v] = true;
    now += sz[v];
    for (auto [to, ww]: g[v]) {
        if (!used[to] && ww >= wnow) {
            dfs(to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> U[i] >> V[i] >> W[i];
        --U[i], --V[i];
        prv[i] = i;
    }
    int q;
    cin >> q;
    vector<array<int, 3>> qu(q + m); //w, type, i
    for (int i = 0; i < q; ++i) {
        cin >> tp[i] >> x[i] >> y[i];
        --x[i];
        qu[i + m] = {-y[i], tp[i], i + m};
        if (tp[i] == 1) {
            nxt[prv[x[i]]] = i;
            prvv[i] = prv[x[i]];
            prv[x[i]] = i + m;
        }
    }
    for (int i = 0; i < m; ++i) {
        nxt[prv[i]] = infI;
        qu[i] = {-W[i], 1, i};
    }
    sort(all(qu));
    for (int i = 0; i < q; i += B) {
        int r = min(i + B, q);
        init(n);
        for (auto t: qu) {
            if (t[1] == 1 && nxt[t[2]] >= r) {
                if (t[2] >= m) {
                    int id = t[2] - m;
                    if (id < i) {
                        mrg(U[x[id]], V[x[id]]);
                    }
                } else {
                    mrg(U[t[2]], V[t[2]]);
                }
            } else if (t[1] == 2) {
                int j = t[2] - m;
                if (j < i || j >= r) continue;
                for (int k = j; k >= i; --k) {
                    if (tp[k] == 1 && !nww[x[k]]) {
                        nww[x[k]] = true;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].emplace_back(b, y[k]), g[b].emplace_back(a, y[k]);
                    }
                }
                for (int k = j; k < r; ++k) {
                    if (tp[k] == 1 && !nww[x[k]]) {
                        int z = prvv[k];
                        int w;
                        if (z >= m) {
                            w = y[z - m];
                        } else {
                            w = W[z];
                        }
                        nww[x[k]] = true;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].emplace_back(b, w), g[b].emplace_back(a, w);
                    }
                }
                wnow = y[j];
                dfs(get(x[j]));
                ans[j] = now;
                now = 0;
                for (int z: vis) {
                    used[z] = false;
                }
                vis.clear();
                for (int k = r - 1; k >= i; --k) {
                    if (tp[k] == 1 && nww[x[k]]) {
                        nww[x[k]] = false;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].clear(), g[b].clear();
                    }
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        if (tp[i] == 2) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 44 ms 2152 KB Output is correct
4 Correct 11 ms 1932 KB Output is correct
5 Correct 26 ms 2124 KB Output is correct
6 Correct 24 ms 2072 KB Output is correct
7 Correct 27 ms 1996 KB Output is correct
8 Correct 26 ms 2072 KB Output is correct
9 Correct 27 ms 1900 KB Output is correct
10 Correct 27 ms 2044 KB Output is correct
11 Correct 24 ms 2040 KB Output is correct
12 Correct 23 ms 2064 KB Output is correct
13 Correct 30 ms 2004 KB Output is correct
14 Correct 29 ms 2064 KB Output is correct
15 Correct 29 ms 2044 KB Output is correct
16 Correct 25 ms 2032 KB Output is correct
17 Correct 26 ms 1920 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1624 ms 11376 KB Output is correct
2 Correct 1614 ms 11380 KB Output is correct
3 Correct 1586 ms 11388 KB Output is correct
4 Correct 1578 ms 11472 KB Output is correct
5 Correct 1594 ms 11580 KB Output is correct
6 Correct 1661 ms 10168 KB Output is correct
7 Correct 1547 ms 10156 KB Output is correct
8 Correct 1560 ms 10220 KB Output is correct
9 Correct 175 ms 5752 KB Output is correct
10 Correct 1219 ms 10048 KB Output is correct
11 Correct 1175 ms 10132 KB Output is correct
12 Correct 805 ms 10064 KB Output is correct
13 Correct 1054 ms 10428 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 9876 KB Output is correct
2 Correct 960 ms 7372 KB Output is correct
3 Correct 1360 ms 9704 KB Output is correct
4 Correct 1372 ms 9868 KB Output is correct
5 Correct 167 ms 5792 KB Output is correct
6 Correct 1380 ms 9680 KB Output is correct
7 Correct 1351 ms 9664 KB Output is correct
8 Correct 1408 ms 9676 KB Output is correct
9 Correct 808 ms 9280 KB Output is correct
10 Correct 842 ms 9384 KB Output is correct
11 Correct 982 ms 9684 KB Output is correct
12 Correct 952 ms 9828 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 12008 KB Output is correct
2 Correct 187 ms 5776 KB Output is correct
3 Correct 86 ms 6732 KB Output is correct
4 Correct 103 ms 6868 KB Output is correct
5 Correct 604 ms 10520 KB Output is correct
6 Correct 1146 ms 12012 KB Output is correct
7 Correct 649 ms 10584 KB Output is correct
8 Correct 764 ms 9052 KB Output is correct
9 Correct 699 ms 9184 KB Output is correct
10 Correct 638 ms 9124 KB Output is correct
11 Correct 1097 ms 10428 KB Output is correct
12 Correct 1072 ms 10576 KB Output is correct
13 Correct 933 ms 10476 KB Output is correct
14 Correct 659 ms 10616 KB Output is correct
15 Correct 571 ms 10564 KB Output is correct
16 Correct 1209 ms 11948 KB Output is correct
17 Correct 1283 ms 11900 KB Output is correct
18 Correct 1270 ms 11976 KB Output is correct
19 Correct 1270 ms 11964 KB Output is correct
20 Correct 1008 ms 10980 KB Output is correct
21 Correct 972 ms 10932 KB Output is correct
22 Correct 1047 ms 11764 KB Output is correct
23 Correct 747 ms 9768 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1624 ms 11376 KB Output is correct
2 Correct 1614 ms 11380 KB Output is correct
3 Correct 1586 ms 11388 KB Output is correct
4 Correct 1578 ms 11472 KB Output is correct
5 Correct 1594 ms 11580 KB Output is correct
6 Correct 1661 ms 10168 KB Output is correct
7 Correct 1547 ms 10156 KB Output is correct
8 Correct 1560 ms 10220 KB Output is correct
9 Correct 175 ms 5752 KB Output is correct
10 Correct 1219 ms 10048 KB Output is correct
11 Correct 1175 ms 10132 KB Output is correct
12 Correct 805 ms 10064 KB Output is correct
13 Correct 1054 ms 10428 KB Output is correct
14 Correct 1392 ms 9876 KB Output is correct
15 Correct 960 ms 7372 KB Output is correct
16 Correct 1360 ms 9704 KB Output is correct
17 Correct 1372 ms 9868 KB Output is correct
18 Correct 167 ms 5792 KB Output is correct
19 Correct 1380 ms 9680 KB Output is correct
20 Correct 1351 ms 9664 KB Output is correct
21 Correct 1408 ms 9676 KB Output is correct
22 Correct 808 ms 9280 KB Output is correct
23 Correct 842 ms 9384 KB Output is correct
24 Correct 982 ms 9684 KB Output is correct
25 Correct 952 ms 9828 KB Output is correct
26 Correct 1821 ms 11276 KB Output is correct
27 Correct 1812 ms 11228 KB Output is correct
28 Correct 1769 ms 11408 KB Output is correct
29 Correct 1612 ms 11216 KB Output is correct
30 Correct 1901 ms 11220 KB Output is correct
31 Correct 1911 ms 11260 KB Output is correct
32 Correct 1893 ms 11224 KB Output is correct
33 Correct 1869 ms 11368 KB Output is correct
34 Correct 1887 ms 11348 KB Output is correct
35 Correct 1869 ms 11352 KB Output is correct
36 Correct 1799 ms 11252 KB Output is correct
37 Correct 1816 ms 11376 KB Output is correct
38 Correct 1816 ms 11212 KB Output is correct
39 Correct 1072 ms 10628 KB Output is correct
40 Correct 1018 ms 10700 KB Output is correct
41 Correct 990 ms 10756 KB Output is correct
42 Correct 1251 ms 11372 KB Output is correct
43 Correct 1227 ms 11344 KB Output is correct
44 Correct 1190 ms 11388 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 44 ms 2152 KB Output is correct
4 Correct 11 ms 1932 KB Output is correct
5 Correct 26 ms 2124 KB Output is correct
6 Correct 24 ms 2072 KB Output is correct
7 Correct 27 ms 1996 KB Output is correct
8 Correct 26 ms 2072 KB Output is correct
9 Correct 27 ms 1900 KB Output is correct
10 Correct 27 ms 2044 KB Output is correct
11 Correct 24 ms 2040 KB Output is correct
12 Correct 23 ms 2064 KB Output is correct
13 Correct 30 ms 2004 KB Output is correct
14 Correct 29 ms 2064 KB Output is correct
15 Correct 29 ms 2044 KB Output is correct
16 Correct 25 ms 2032 KB Output is correct
17 Correct 26 ms 1920 KB Output is correct
18 Correct 1624 ms 11376 KB Output is correct
19 Correct 1614 ms 11380 KB Output is correct
20 Correct 1586 ms 11388 KB Output is correct
21 Correct 1578 ms 11472 KB Output is correct
22 Correct 1594 ms 11580 KB Output is correct
23 Correct 1661 ms 10168 KB Output is correct
24 Correct 1547 ms 10156 KB Output is correct
25 Correct 1560 ms 10220 KB Output is correct
26 Correct 175 ms 5752 KB Output is correct
27 Correct 1219 ms 10048 KB Output is correct
28 Correct 1175 ms 10132 KB Output is correct
29 Correct 805 ms 10064 KB Output is correct
30 Correct 1054 ms 10428 KB Output is correct
31 Correct 1392 ms 9876 KB Output is correct
32 Correct 960 ms 7372 KB Output is correct
33 Correct 1360 ms 9704 KB Output is correct
34 Correct 1372 ms 9868 KB Output is correct
35 Correct 167 ms 5792 KB Output is correct
36 Correct 1380 ms 9680 KB Output is correct
37 Correct 1351 ms 9664 KB Output is correct
38 Correct 1408 ms 9676 KB Output is correct
39 Correct 808 ms 9280 KB Output is correct
40 Correct 842 ms 9384 KB Output is correct
41 Correct 982 ms 9684 KB Output is correct
42 Correct 952 ms 9828 KB Output is correct
43 Correct 1126 ms 12008 KB Output is correct
44 Correct 187 ms 5776 KB Output is correct
45 Correct 86 ms 6732 KB Output is correct
46 Correct 103 ms 6868 KB Output is correct
47 Correct 604 ms 10520 KB Output is correct
48 Correct 1146 ms 12012 KB Output is correct
49 Correct 649 ms 10584 KB Output is correct
50 Correct 764 ms 9052 KB Output is correct
51 Correct 699 ms 9184 KB Output is correct
52 Correct 638 ms 9124 KB Output is correct
53 Correct 1097 ms 10428 KB Output is correct
54 Correct 1072 ms 10576 KB Output is correct
55 Correct 933 ms 10476 KB Output is correct
56 Correct 659 ms 10616 KB Output is correct
57 Correct 571 ms 10564 KB Output is correct
58 Correct 1209 ms 11948 KB Output is correct
59 Correct 1283 ms 11900 KB Output is correct
60 Correct 1270 ms 11976 KB Output is correct
61 Correct 1270 ms 11964 KB Output is correct
62 Correct 1008 ms 10980 KB Output is correct
63 Correct 972 ms 10932 KB Output is correct
64 Correct 1047 ms 11764 KB Output is correct
65 Correct 747 ms 9768 KB Output is correct
66 Correct 1821 ms 11276 KB Output is correct
67 Correct 1812 ms 11228 KB Output is correct
68 Correct 1769 ms 11408 KB Output is correct
69 Correct 1612 ms 11216 KB Output is correct
70 Correct 1901 ms 11220 KB Output is correct
71 Correct 1911 ms 11260 KB Output is correct
72 Correct 1893 ms 11224 KB Output is correct
73 Correct 1869 ms 11368 KB Output is correct
74 Correct 1887 ms 11348 KB Output is correct
75 Correct 1869 ms 11352 KB Output is correct
76 Correct 1799 ms 11252 KB Output is correct
77 Correct 1816 ms 11376 KB Output is correct
78 Correct 1816 ms 11212 KB Output is correct
79 Correct 1072 ms 10628 KB Output is correct
80 Correct 1018 ms 10700 KB Output is correct
81 Correct 990 ms 10756 KB Output is correct
82 Correct 1251 ms 11372 KB Output is correct
83 Correct 1227 ms 11344 KB Output is correct
84 Correct 1190 ms 11388 KB Output is correct
85 Correct 2082 ms 14168 KB Output is correct
86 Correct 124 ms 7036 KB Output is correct
87 Correct 109 ms 7112 KB Output is correct
88 Correct 1324 ms 12568 KB Output is correct
89 Correct 2060 ms 14148 KB Output is correct
90 Correct 1291 ms 11956 KB Output is correct
91 Correct 1816 ms 11236 KB Output is correct
92 Correct 1798 ms 11436 KB Output is correct
93 Correct 1675 ms 10444 KB Output is correct
94 Correct 2063 ms 13056 KB Output is correct
95 Correct 2102 ms 13024 KB Output is correct
96 Correct 1688 ms 11832 KB Output is correct
97 Correct 808 ms 11600 KB Output is correct
98 Correct 943 ms 11984 KB Output is correct
99 Correct 2199 ms 14244 KB Output is correct
100 Correct 2327 ms 14176 KB Output is correct
101 Correct 2387 ms 14168 KB Output is correct
102 Correct 2319 ms 14152 KB Output is correct
103 Correct 1747 ms 12000 KB Output is correct
104 Correct 1737 ms 12168 KB Output is correct
105 Correct 1538 ms 12276 KB Output is correct
106 Correct 1295 ms 12412 KB Output is correct
107 Correct 1200 ms 11836 KB Output is correct
108 Correct 1834 ms 12620 KB Output is correct
109 Correct 1314 ms 10548 KB Output is correct