Submission #1271784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271784		thuhienne	다리 (APIO19_bridges)	C++17	0 / 100	3095 ms	6032 KiB

bridges

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

/*
   DSU rollback + block decomposition
   Cải tiến so với code gốc:
   - dùng mảng tĩnh cho record stack (không dùng vector)
   - tag/version để mark changed edges trong block (reset O(1))
   - một vài micro-optimizations
*/

#define SIZE __size__
#define UNION __union__
#define DATA __data__

const int MAXM = 100009;
const int MAXQ = 100009;
const int MAXN = 100009;
const int CAN = 350; // kích thước block, có thể tune

int n, m, q;

struct Edge {
    int u, v, w, index;
} edge[MAXM];

bool dummy_changed[MAXM]; // không dùng trực tiếp, dùng tag below

// tag/version để biết edge bị thay trong block
int tag_changed[MAXM];
int cur_tag = 1;

// để lưu lần đầu xử lý trong block (firsttime logic)
int firsttime[MAXM];
int uniq = 1;

int root_arr[MAXN], sz_arr[MAXN];

int getroot_simple(int x) {
    return (root_arr[x] == x ? x : root_arr[x] = getroot_simple(root_arr[x]));
}
void union_simple(int a, int b) {
    a = getroot_simple(a);
    b = getroot_simple(b);
    if (a == b) return;
    root_arr[a] = b;
    sz_arr[b] += sz_arr[a];
}

// DSU rollback record entry (mảng tĩnh)
struct REC {
    int node;         // node index whose parent/size changed
    int root_before;  // previous parent
    int size_before;  // previous size[node]
};
const int MAX_RECORDS = 2000000; // tune nếu cần
REC record_stack[MAX_RECORDS];
int rec_top = 0;

// rollback-aware getroot (path comp without destroying info)
int getroot_record(int x) {
    while (root_arr[x] != x) x = root_arr[x];
    return x;
}

// version of getroot that records changes for rollback
int getroot_and_record(int x) {
    if (root_arr[x] == x) return x;
    int p = getroot_and_record(root_arr[x]);
    // record current node's parent and size before changing
    record_stack[rec_top++] = { x, root_arr[x], sz_arr[x] };
    root_arr[x] = p;
    return p;
}

void union_record(int a, int b) {
    a = getroot_and_record(a);
    b = getroot_and_record(b);
    if (a == b) return;
    // record a before linking
    record_stack[rec_top++] = { a, root_arr[a], sz_arr[a] };
    root_arr[a] = b;
    // record b before size update
    record_stack[rec_top++] = { b, root_arr[b], sz_arr[b] };
    sz_arr[b] += sz_arr[a];
}

void rollback_to(int old_top) {
    while (rec_top > old_top) {
        --rec_top;
        REC r = record_stack[rec_top];
        root_arr[r.node] = r.root_before;
        sz_arr[r.node] = r.size_before;
    }
}

struct Query {
    int op, x, y, index;
} ask[MAXQ];

Edge bridges[MAXQ]; // store edges for updates inside block
int answer[MAXQ];

// helper array for sorting edges by weight (indices)
int order_idx[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        edge[i].index = i;
    }
    cin >> q;
    
    // init tags/firsttime
    for (int i = 1; i <= m; ++i) {
        tag_changed[i] = 0;
        firsttime[i] = 0;
    }
    
    // process queries block by block
    int block_id = 0;
    for (int start = 1; start <= q; start += CAN) {
        ++block_id;
        int l = start;
        int r = min(q, start + CAN - 1);
        
        // read block queries
        for (int i = l; i <= r; ++i) {
            cin >> ask[i].op >> ask[i].x >> ask[i].y;
            ask[i].index = i;
            if (ask[i].op == 1) {
                // mark changed using tag
                tag_changed[ask[i].x] = block_id;
                bridges[i] = edge[ask[i].x]; // store prior edge state
            }
        }
        
        // Build an index array of edges sorted by current weight
        // (We will skip edges that are changed in this block via tag_changed)
        for (int i = 1; i <= m; ++i) order_idx[i-1] = i;
        sort(order_idx, order_idx + m, [&](int a, int b){
            if (edge[a].w != edge[b].w) return edge[a].w < edge[b].w;
            return a < b;
        });
        
        // init DSU
        for (int i = 1; i <= n; ++i) {
            root_arr[i] = i; sz_arr[i] = 1;
        }
        
        // collect queries of type 2 (contain) with their index and sort descending by y
        static Query contain[CAN + 5];
        int contain_cnt = 0;
        for (int i = l; i <= r; ++i) {
            if (ask[i].op == 2) contain[contain_cnt++] = ask[i];
        }
        sort(contain, contain + contain_cnt, [](const Query &a, const Query &b){
            return a.y > b.y; // descending by y
        });
        
        // process contain queries using pointer on sorted edges (descending)
        int ptr = m - 1; // order_idx[ptr] is current largest weight candidate
        for (int ci = 0; ci < contain_cnt; ++ci) {
            Query d = contain[ci];
            int minimum = d.y;
            int island = d.x;
            
            // add all global edges (not changed in this block) with w >= minimum
            while (ptr >= 0 && edge[order_idx[ptr]].w >= minimum) {
                int ei = order_idx[ptr];
                if (tag_changed[ei] != block_id) {
                    union_simple(edge[ei].u, edge[ei].v);
                }
                --ptr;
            }
            
            // now we need to incorporate changed edges from this block
            int old_top = rec_top;
            ++uniq;
            // scan left of query in block
            for (int i = d.index - 1; i >= l; --i) {
                if (ask[i].op != 1) continue;
                Edge br = bridges[i];
                int w_for_this = ask[i].y;
                int idx = br.index;
                if (firsttime[idx] == uniq) continue;
                firsttime[idx] = uniq;
                if (w_for_this >= minimum) union_record(br.u, br.v);
            }
            // scan right of query in block
            for (int i = d.index + 1; i <= r; ++i) {
                if (ask[i].op != 1) continue;
                Edge br = bridges[i];
                int w_for_this = ask[i].y;
                int idx = br.index;
                if (firsttime[idx] == uniq) continue;
                firsttime[idx] = uniq;
                if (br.w >= minimum) union_record(br.u, br.v);
            }
            // but note: for updates that appear in block, there are two relevant weights:
            // - for updates before d.index, the effective weight is ask[i].y (the new weight)
            // - for updates after d.index, the effective weight is br.w (previous weight)
            // The code above handles that: left uses ask[i].y, right uses br.w.
            
            // answer: size of component containing island
            int comp_root = getroot_simple(island);
            // However, some nodes may have been path-compressed in union_record; to get correct size,
            // we should get root via getroot_and_record or getroot_simple (we maintained sz only for roots)
            answer[d.index] = sz_arr[getroot_simple(island)];
            
            // rollback to old_top
            rollback_to(old_top);
        }
        
        // after processing block, apply updates (op==1) permanently to edges
        for (int i = l; i <= r; ++i) {
            if (ask[i].op == 1) {
                int ei = ask[i].x;
                edge[ei].w = ask[i].y;
                // clear tag by just leaving it; next block uses different block_id
            }
        }
    }
    
    // print answers for op==2
    for (int i = 1; i <= q; ++i) {
        if (ask[i].op == 2) {
            cout << answer[i] << '\n';
        }
    }
    return 0;
}

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