Submission #1190828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190828		jioung	Bridges (APIO19_bridges)	C++20	59 / 100	3087 ms	8436 KiB

bridges

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

#define fi first
#define se second
#define NAME ""
#define eb emplace_back
#define pii pair<int, int>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define FORD(i, a, b, x) for (int i = (a), _b = (b); i <= _b; i += x)

const int MAX = 100005, BLOCK = sqrt(MAX) + 1, LOG = __lg(MAX) + 1, mod = 1e9 + 7;
const int INF = 1e9;
typedef long long ll;
namespace Solution
{
    int n, m, q, u[MAX], v[MAX], w[MAX];
    int x[MAX], y[MAX], t[MAX], vis[MAX];
    int ans[MAX], mp[MAX];
    class DSU {
    public:
        vector<int> parent, size;
        vector<tuple<int, int, int, int>> history;
        DSU(int n) {
            parent.resize(n + 1);
            size.resize(n + 1, 1);
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }
        int find(int x) {
            if (parent[x] != x) {
                return find(parent[x]);
            }
            return parent[x];
        }
        void unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                history.push_back({-1, -1, -1, -1});
                return;
            }
            if (size[x] < size[y]) swap(x, y);
            history.push_back({y, parent[y], x, size[x]});
            parent[y] = x;
            size[x] += size[y];
        }
        void rollback(int snap) {
            while ((int)history.size() > snap) {
                auto [y, old_parent, x_root, old_size] = history.back();
                history.pop_back();
                if (y == -1) continue;
                parent[y] = old_parent;
                size[x_root] = old_size;
            }
        }
    };
    void solve() {
        cin >> n >> m;
        FOR(i, 1, m) {
            cin >> u[i] >> v[i] >> w[i];
        }
        cin >> q;
        FOR(i, 1, q) {
            cin >> t[i] >> x[i] >> y[i];
        }
        FORD(k, 1, q, BLOCK) {
            int l = k, r = min(k + BLOCK - 1, q);
            vector<tuple<int, int, int>> ask;
            vector<tuple<int, int, int>> change;
            FOR(i, l, r) {
                if (t[i] == 1) {
                    if(!vis[x[i]]) {
                        change.push_back({w[x[i]], x[i], 0});
                    } 
                    vis[x[i]] = 1;
                    w[x[i]] = y[i];
                    change.push_back({w[x[i]], x[i], i});
                } else {
                    ask.push_back({x[i], y[i], i});
                }
            }
            vector<tuple<int, int, int>> unchange;
            FOR(i, 1, m) {
                if (!vis[i]) {
                    unchange.push_back({w[i], u[i], v[i]});
                }
            }
            reverse(change.begin(), change.end());
            sort(unchange.begin(), unchange.end(), [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
                return get<0>(a) < get<0>(b);
            });
            sort(ask.begin(),  ask.end(), [](const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
                return get<1>(a) > get<1>(b);
            });
            DSU dsu(n);
            for (auto [uu, ww, id] : ask) {
                while (!unchange.empty() && get<0>(unchange.back()) >= ww) {
                    auto [cost, i, j] = unchange.back();
                    unchange.pop_back();
                    dsu.unite(i, j);
                }
                int snap = dsu.history.size();
                //cerr << id << ' ' << "snap: " << snap << '\n';
                for (auto [wei, x, idx] : change) {
                    int i = u[x], j = v[x];
                    if (wei >= ww && idx <= id && mp[x] == 0) {
                        dsu.unite(i, j);
                    }
                    if (idx <= id) {
                        mp[x] = 1;
                    }
                }
                for (auto [wei, x, idx] : change) {
                    if (idx <= id) {
                        mp[x] = 0;
                    }
                }
                ans[id] = dsu.size[dsu.find(uu)];
                //cerr << id << ' ' << "rollback: " << dsu.history.size() << '\n';
                dsu.rollback(snap);
            }
            for (auto &c : change) {
                int idx = get<2>(c);
                vis[x[idx]] = 0;
            }
        }
        FOR(i, 1, q) {
            if (t[i] == 2) {
                cout << ans[i] << '\n';
            }
        }
    }
}

signed main()
{
    if (fopen(NAME ".inp", "r"))
    {
        freopen(NAME ".inp", "r", stdin);
        freopen(NAME ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    while (T--)
    {
        Solution::solve();
    }
    return 0;
}

Compilation message (stderr)

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

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