Submission #706943

#	Time	Username	Problem	Language	Result	Execution time	Memory
706943		jhwest2	Bridges (APIO19_bridges)	C++14	73 / 100	3038 ms	28288 KiB

bridges

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

const int N = 101010;
const int B = 400;

int n, m, q, u[N], v[N], w[N], s[N], t[N], y[N], z[N], weight[N], ans[N];
bool used[N], vis[N];
vector<int> g[N];

struct dsu {
    int pp[N], sz[N];

    void init() {
        iota(pp, pp + N / 2, 0);
        fill(sz, sz + N / 2, 1);
    }
    int find(int a) {
        return pp[a] = ((pp[a] == a) ? a : find(pp[a]));
    }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            pp[b] = a;
            sz[a] += sz[b];
        }
    }
} d1;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> y[i] >> z[i];
    }
    for (int i = 1; i <= m; i++)
        s[i] = i;

    vector<int> upd, ask;
    for (int x = 1; x <= q; x++) {
        if (t[x] == 1)
            upd.push_back(x), used[y[x]] = 1;
        else
            ask.push_back(x);
        
        if (upd.size() == B || x == q) {
            sort(s + 1, s + 1 + m, [&](int i, int j) {
                return w[i] > w[j];
            });

            sort(ask.begin(), ask.end(), [&](int i, int j) {
                return z[i] > z[j];
            });
            
            vector<int> edges;
            for (int i : upd)
                edges.push_back(y[i]);
            
            sort(edges.begin(), edges.end());
            edges.erase(unique(edges.begin(), edges.end()), edges.end());

            d1.init();
            int p = 1;
            for (auto i : ask) {
                while (p <= m && w[s[p]] >= z[i]) {
                    if (!used[s[p]]) 
                        d1.merge(u[s[p]], v[s[p]]);
                    ++p;
                }

                for (int j : edges) 
                    weight[j] = w[j];
                
                for (int j : upd) {
                    if (j <= i)
                        weight[y[j]] = z[j];
                }

                for (int j : edges) {
                    int a = d1.find(u[j]);
                    int b = d1.find(v[j]);

                    if (weight[j] >= z[i]) {
                        g[a].push_back(b);
                        g[b].push_back(a);
                    }
                }

                int x = d1.find(y[i]);

                vector<int> q;
                q.push_back(x);

                int res = 0;
                while (!q.empty()) {
                    int v = q.back(); q.pop_back();
                    if (vis[v])
                        continue;
                    
                    vis[v] = 1;
                    res += d1.sz[v];

                    for (int x : g[v])
                        q.push_back(x);
                }
                vis[x] = 0;
                
                for (int j : edges) {
                    int a = d1.find(u[j]);
                    int b = d1.find(v[j]);

                    g[a].clear();
                    g[b].clear();
                    vis[a] = 0;
                    vis[b] = 0;
                }
                ans[i] = res;
            }

            for (auto i : upd) {
                used[y[i]] = 0;
                w[y[i]] = z[i];
            }

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

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

// const int N = 101010;
// const int B = 200;

// int n, m, q, u[N], v[N], w[N], s[N], t[N], y[N], z[N], upd[N], ask[N], edges[N], weight[N], ans[N];
// bool used[N], vis[N], vv[N];
// vector<int> g[N];

// struct dsu {
//     int pp[N], sz[N];

//     void init() {
//         iota(pp, pp + N, 0);
//         fill(sz, sz + N, 1);
//     }
//     int find(int a) {
//         return pp[a] = ((pp[a] == a) ? a : find(pp[a]));
//     }
//     void merge(int a, int b) {
//         a = find(a); b = find(b);
//         if (a != b) {
//             pp[b] = a;
//             sz[a] += sz[b];
//         }
//     }
// } d1;

// mt19937 rnd(1557);
// int rng(int l, int r) {
//     return uniform_int_distribution<int>(l, r)(rnd);
// }
// int main() {
//     cin.tie(0); ios_base::sync_with_stdio(0);
//     cin >> n >> m;
//     // n = 50000;
//     // m = 100000;

//     for (int i = 1; i <= m; i++) {
//         cin >> u[i] >> v[i] >> w[i];
//         // u[i] = rng(1, n - 1);
//         // v[i] = rng(u[i] + 1, n);
//         // w[i] = rng(1, 100);
//     }
//     cin >> q;
//     // q = 10000;
//     for (int i = 1; i <= q; i++) {
//         cin >> t[i] >> y[i] >> z[i];
//         // t[i] = rng(1, 2);
//         // y[i] = rng(1, n);
//         // z[i] = rng(1, 100);
//     }
//     for (int i = 1; i <= m; i++)
//         s[i] = i;
    
//     int usz = 0, asz = 0;
//     for (int x = 1; x <= q; x++) {
//         if (t[x] == 1)
//             upd[usz++] = x, used[y[x]] = 1;
//         else
//             ask[asz++] = x;
        
//         if (usz == B || x == q) {
//             sort(s + 1, s + 1 + m, [&](int i, int j) {
//                 return w[i] > w[j];
//             });

//             sort(ask, ask + asz, [&](int i, int j) {
//                 return z[i] > z[j];
//             });
            
//             int esz = 0;
//             for (int i : upd)
//                 edges[esz++] = y[i];
            
//             sort(edges, edges + esz);
//             esz = unique(edges, edges + esz) - edges;

//             for (int j = 0; j < esz; j++)
//                 weight[edges[j]] = w[edges[j]];

//             d1.init();
//             int p = 1;
//             for (auto i : ask) {
//                 while (p <= m && w[s[p]] >= z[i]) {
//                     if (!used[s[p]]) 
//                         d1.merge(u[s[p]], v[s[p]]);
//                     ++p;
//                 }

//                 for (int j = 0; j < usz; j++) {
//                     if (upd[j] <= i)
//                         w[y[upd[j]]] = z[upd[j]];
//                 }

//                 for (int j = 0; j < esz; j++) {
//                     int a = d1.find(u[edges[j]]);
//                     int b = d1.find(v[edges[j]]);

//                     if (w[edges[j]] >= z[i]) {
//                         g[a].push_back(b);
//                         g[b].push_back(a);
//                     }
//                 }

//                 int x = d1.find(y[i]);
//                 int vsz = 1;
//                 vv[0] = x;

//                 int res = 0;
//                 while (vsz) {
//                     int v = vv[--vsz];
//                     if (vis[v])
//                         continue;
                    
//                     vis[v] = 1;
//                     res += d1.sz[v];

//                     for (int x : g[v]) 
//                         vv[vsz++] = x;
//                 }
//                 ans[i] = res;

//                 for (int j = 0; j < esz; j++) {
//                     int a = d1.find(u[edges[j]]);

//                     w[edges[j]] = weight[edges[j]];
//                     g[a].clear();
//                     vis[a] = 0;
//                 }
//             }

//             for (int i = 0; i < usz; i++) {
//                 used[upd[i]] = 0;
//                 w[y[upd[i]]] = z[upd[i]];
//             }
//         }
//     }
//     for (int i = 1; i <= q; i++) {
//         if (t[i] == 2)
//             cout << ans[i] << '\n';
//     }
// }

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