Submission #755408

#	Time	Username	Problem	Language	Result	Execution time	Memory
755408		fanwen	Bridges (APIO19_bridges)	C++17	59 / 100	3038 ms	6888 KiB

bridges

/**
 *      author : pham van sam 
 *      created : 10 June 2023 (Saturday)
 **/
#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

struct disjoint_set_union_rollback {
    vector <int> lab, sz;
    stack <int> save;
    int n;
    disjoint_set_union_rollback(int _n = 0) : n(_n) {
        lab.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        iota(ALL(lab), 0);
    }

    void clear() {
        while((int) save.size()) save.pop();
        fill(ALL(sz), 1);
        iota(ALL(lab), 0);
    }

    int find(int u) {
        assert(u <= n);
        // cout << u << '\n';
        return lab[u] == u ? u : find(lab[u]);
    }

    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        lab[v] = u;
        save.push(v);
        return true;
    } 
    void rollback(int ptr) {
        while((int) save.size() > ptr) {
            int v = save.top(); save.pop();
            sz[lab[v]] -= sz[v];
            lab[v] = v; 
        }
    }
};

struct Edge {
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
    int get(int x) { return u ^ v ^ x; }
};

const int MAXN = 1e5 + 5;

int N, M, Q, type[MAXN], x[MAXN], y[MAXN], ans[MAXN];
vector <int> need[MAXN];


void process(void) {
    
}

signed main() {

    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    
    cin >> N >> M;
    vector <Edge> edges(M + 1);
    FOR(i, 1, M) cin >> edges[i].u >> edges[i].v >> edges[i].w;
    cin >> Q;
    FOR(i, 1, Q) cin >> type[i] >> x[i] >> y[i];
    const int Block = sqrt(Q - 1) + 1;

    disjoint_set_union_rollback dsu(N);
    for (int l = 1; l <= Q; l += Block) {
        int r = min(Q, l + Block - 1);
        // dsu = disjoint_set_union_rollback(N);
        dsu.clear();
        vector <bool> dd(M + 1);
        vector <int> update, questions, unchanged;
        FOR(i, l, r) if(type[i] == 1) {
            dd[x[i]] = true;
            update.push_back(x[i]);
        } else questions.push_back(i);

        FOR(i, 1, M) if(!dd[i]) unchanged.push_back(i);
        FOR(i, l, r) if(type[i] == 1) edges[x[i]].w = y[i];
        else {
            need[i - l].clear();
            for (auto x : update) if(edges[x].w >= y[i]) need[i - l].push_back(x);
        }
        sort(ALL(unchanged), [&](int i, int j) { return edges[i].w > edges[j].w; });
        sort(ALL(questions), [&](int i, int j) { return y[i] > y[j]; });
        int j = 0;
        REP(i, (int) questions.size()) {
            while(j < (int) unchanged.size() && edges[unchanged[j]].w >= y[questions[i]]) {
                dsu.merge(edges[unchanged[j]].u, edges[unchanged[j]].v);
                j++;
            }
            int tmp = (int) dsu.save.size();
            for (auto x : need[questions[i] - l]) {
                dsu.merge(edges[x].u, edges[x].v);
            }
            ans[questions[i]] = dsu.sz[dsu.find(x[questions[i]])];
            dsu.rollback(tmp);
        }
    }
    FOR(i, 1, Q) if(type[i] == 2) cout << ans[i] << '\n';

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(TASK".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