Submission #649155

#	Time	Username	Problem	Language	Result	Execution time	Memory
649155		LeonaRaging	Bridges (APIO19_bridges)	C++14	27 / 100	1717 ms	524288 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 5e4 + 3;
const int INF = 1e9;
const int block = 1e9;

struct Edge {
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
} edges[2 * maxn];

struct Query {
    int t, x, y;
    Query(int t = 0, int x = 0, int y = 0): t(t), x(x), y(y) {}
} quy[2 * maxn];

int n, m, q, res[2 * maxn];
stack<int> st;
bool bad[2 * maxn];
vector<int> upd[2 * maxn], change, unchange, ask;

struct DisjointSet {
    int par[maxn], Rank[maxn];
    int find(int x) {
        while (x != par[x]) x = par[x];
        return x;
    }
    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return 0;
        if (Rank[u] < Rank[v])
            swap(u, v);
        st.push(v);
        Rank[u] += Rank[v];
        par[v] = u;
        return 1;
    }
    void rollback(int x) {
        while ((int)st.size() > x) {
            int u = st.top(); st.pop();
            Rank[par[u]] -= Rank[u];
            par[u] = u;
        }
    }
} Dsu;

void reset() {
    for (int i = 1; i <= n; i++) {
        Dsu.par[i] = i; Dsu.Rank[i] = 1;
    }
    for (int i = 1; i <= m; i++)
        bad[i] = false;
    vector<int>().swap(change);
    vector<int>().swap(unchange);
    vector<int>().swap(ask);

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }   
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int t, x, y; cin >> t >> x >> y;
        quy[i] = {t, x, y};
    }
    for (int l = 1; l <= q; l += block) {
        int r = min(l + block - 1, q);
        reset();
        for (int i = l; i <= r; i++)
            if (quy[i].t == 1) 
                bad[quy[i].x] = true;
        for (int i = 1; i <= m; i++)
            if (!bad[i]) unchange.pb(i);
            else change.pb(i);
        for (int i = l; i <= r; i++) {
            if (quy[i].t == 1)
                edges[quy[i].x].w = quy[i].y;
            else {
                ask.pb(i);
                vector<int>().swap(upd[i]);
                for (auto k : change)
                    if (edges[k].w >= quy[i].y)
                        upd[i].pb(k);
            }
        }
        sort(unchange.begin(), unchange.end(),[&] (int i, int j) {
            return edges[i].w > edges[j].w;
        });
        sort(ask.begin(), ask.end(),[&](int i, int j) {
            return quy[i].y > quy[j].y;
        });
        int pos = 0;
        for (int i : ask) {
            while (pos < (int)unchange.size() && quy[i].y <= edges[unchange[pos]].w) {
                Dsu.join(edges[unchange[pos]].u, edges[unchange[pos]].v);
                pos++;
            }
            int sz = st.size();
            for (int k : upd[i])
                Dsu.join(edges[k].u, edges[k].v);
            quy[i].x = Dsu.find(quy[i].x);
            res[i] = Dsu.Rank[quy[i].x];
            Dsu.rollback(sz); 
        }
    }
    for (int i = 1; i <= q; i++)
        if (res[i]) cout << res[i] << '\n';
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27