Submission #1177753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177753		sasde	Bridges (APIO19_bridges)	C++17	0 / 100	695 ms	3776 KiB

bridges

#include<bits/stdc++.h>
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N = 5e4+5, sq = 450;

stack<ii> zz;
int r[N], ver[N], curVer = 0;  // Dùng phiên bản để tránh memset

void reset() { ++curVer; }

int acs(int u) {
    if (ver[u] != curVer) {
        ver[u] = curVer;
        r[u] = -1;
        return u;
    }
    return (r[u] < 0) ? u : (r[u] = acs(r[u]));
}

void join(int u, int v, int i) {
    u = acs(u), v = acs(v);
    if (u == v) return;
    if (r[u] > r[v]) swap(u, v);
    if (i) zz.push({v, r[v]});
    r[u] += r[v];
    r[v] = u;
}

void rollback() {
    while (!zz.empty()) {
        auto [v, rv] = zz.top();
        zz.pop();
        r[v] = rv;
    }
}

int n, m, ans[N];
struct pt1 { int u, v, w; } b[2 * N];
struct pt2 { int t, u, w; } c[2 * N];

bool k[N];
int k1[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> b[i].u >> b[i].v >> b[i].w;
    int q;
    cin >> q;
    for (int test = 1; test <= q; ++test) cin >> c[test].t >> c[test].u >> c[test].w;

    for (int st = 1; st <= q; st += sq) {
        vector<int> jo, nojo, res;
        int test = min(q, st + sq - 1);

        for (int i = st; i <= test; ++i) {
            if (c[i].t == 1) k[c[i].u] = 1;
            else res.emb(i);
        }

        for (int i = 1; i <= m; ++i) {
            if (!k[i]) nojo.emb(i);
            else jo.emb(i);
        }

        sort(res.begin(), res.end(), [](const int &x, const int &y) {
            return c[x].w > c[y].w;
        });
        sort(nojo.begin(), nojo.end(), [](const int &x, const int &y) {
            return b[x].w > b[y].w;
        });

        int j = 0;
        reset();  // Tránh memset
        for (int x : res) {
            while (j < nojo.size() && b[nojo[j]].w >= c[x].w) {
                join(b[nojo[j]].u, b[nojo[j]].v, 0);
                ++j;
            }

            for (int z = st; z < x; ++z) if (c[z].t == 1) k1[c[z].u] = z;
            for (int y : jo) {
                if (k1[y] && c[k1[y]].w >= c[x].w) join(b[y].u, b[y].v, 1);
                else if (b[y].w >= c[x].w) join(b[y].u, b[y].v, 1);
            }

            ans[x] = -r[acs(c[x].u)];
            rollback();
            for (int z = st; z < x; ++z) if (c[z].t == 1) k1[c[z].u] = 0;
        }

        for (int i = st; i <= test; ++i) {
            if (c[i].t == 1) {
                k[c[i].u] = 0;
                b[c[i].u].w = c[i].w;
            }
        }
    }

    for (int i = 1; i <= q; ++i) if (c[i].t == 2) cout << ans[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    solve();
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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