Submission #1105623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105623		Lithanium	Bridges (APIO19_bridges)	C++17	100 / 100	1124 ms	15084 KiB

bridges

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma") 

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

int dsu[50005];
int sz[50005];
int K = 840;

int find(int n) {
    if (dsu[n] == n) return n;
    return dsu[n] = find(dsu[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b);
        dsu[b] = a;
        sz[a] += sz[b];
    }
}

bool change[100005];
int dt[100005][3];
int N, M;
int res[100005];
bool seen[50005];
vector<int> adj[50005];
int CURR = 0;

struct Query {
    int op, a, b;
};

set<tuple<int, int, int>> edges;

void dfs(int n) {
    CURR += sz[n];
    seen[n] = 1;
    for (int i:adj[n]) if (!seen[i]) dfs(i);
}

void solve(vector<Query> &batch) {
    // find which edges are not impacted
    memset(change, 0, sizeof(change));
    vector<tuple<int, int, int>> todo;
    vector<int> changed;
    for (int i = 0; i < batch.size(); i ++) {
        Query Q = batch[i];
        if (Q.op == 1) changed.push_back(Q.a);
        else todo.push_back({Q.b, Q.a, i});
    }
    sort(todo.begin(), todo.end());
    for (int i:changed) {
        edges.erase({dt[i][0], dt[i][1], dt[i][2]});
    }
    auto ptr = edges.begin();
    for (int i = 1; i <= N; i ++) dsu[i] = i, sz[i] = 1;

    // Calculate edges
    int ans[batch.size()] = {0};
    for (auto [w, n, id]:todo) {
        // add all the edges
        while (ptr != edges.end()) {
            auto [a, b, c] = *ptr;
            if (a <= w) {
                merge(b, c);
                ptr ++;
            } else {
                break;
            }
        }
        // find the extra merges
        for (int i:changed) res[i] = dt[i][0];
        for (int i = 0; i < id; i ++) {
            Query Q = batch[i];
            if (Q.op == 1) {
                res[Q.a] = Q.b;
            }
        }
        for (int i:changed) {
            if (res[i] <= w) {
                // make edge
                int t1 = find(dt[i][1]), t2 = find(dt[i][2]);
                adj[t1].push_back(t2);
                adj[t2].push_back(t1);
            }
            res[i] = 0;
        }
        CURR = 0;
        dfs(find(n));
        ans[id] = CURR;
        // clear the result
        seen[find(n)] = 0;
        for (int i:changed) {
            int t1 = find(dt[i][1]), t2 = find(dt[i][2]);
            adj[t1].clear();
            adj[t2].clear();
            seen[t1] = 0;
            seen[t2] = 0;
        }
    }
    for (int i:ans) if (i != 0) cout << i << "\n";
    // push this batch of data over
    for (Query Q:batch) if (Q.op == 1) dt[Q.a][0] = Q.b;
    for (int i:changed) edges.insert({dt[i][0], dt[i][1], dt[i][2]});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    if (M == 100000) K = 820;
    for (int i = 1; i <= M; i ++) {
        cin >> dt[i][1] >> dt[i][2] >> dt[i][0];
        dt[i][0] = -dt[i][0];
        edges.insert({dt[i][0], dt[i][1], dt[i][2]});
    }
    vector<Query> batch;
    int Q;
    cin >> Q;
    auto start = clock();
    int bruh = 0, tot = 0;
    for (int i = 1; i <= Q; i ++) {
        // assert(10*(clock() - start) < CLOCKS_PER_SEC * 19);
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) bruh ++;
        tot ++;
        c = -c;
        batch.push_back({a, b, c});
        if (tot == K) {
            solve(batch);
            batch.clear();
            tot = 0, bruh = 0;
        }
    }
    if (!batch.empty()) solve(batch);
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(std::vector<Query>&)':
bridges.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < batch.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:125:10: warning: unused variable 'start' [-Wunused-variable]
  125 |     auto start = clock();
      |          ^~~~~

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