Submission #511262

#	Time	Username	Problem	Language	Result	Execution time	Memory
511262		blue	Bridges (APIO19_bridges)	C++17	100 / 100	2748 ms	6856 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
using vi = vector<int>;
 
const int rt = 946;
 
int n, m;
vi u, v, w;
 
int q;
vi t;
vi b, r;
vi s, c;
 
struct disjoint_set
{
    vi parent;
    vi subtree;
 
    vector<int> changes;
 
    disjoint_set()
    {
        parent = vi(1+n);
        subtree = vi(1+n, 1);
        for(int i = 0; i <= n; i++) parent[i] = i;
    }
 
    int root(int u)
    {
        while(parent[u] != u) u = parent[u];
        return u;
    }
 
    void join(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v)
        {
            // cerr << "change rejected\n";
            changes.push_back(0);
        }
        else
        {
            if(subtree[u] < subtree[v]) swap(u, v);
            parent[v] = u;
            subtree[u] += subtree[v];
            changes.push_back(v);
            // cerr << "making " << u << " parent of " << v << '\n';
        }
    }
 
    void rollback()
    {
        int c = changes.back();
        changes.pop_back();
        subtree[parent[c]] -= subtree[c];
        parent[c] = c;
    }
 
    int reach(int u)
    {
        return subtree[root(u)];
    }
};
 
 
int wt(int d)
{
    if(d > 0)
    {
        return w[d];
    }
    else
    {
        return c[-d];
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
 
    u = v = w = vi(1+m);
    for(int e = 1; e <= m; e++) cin >> u[e] >> v[e] >> w[e];
 
    cin >> q;
    t = b = r = s = c = vi(q);
    for(int j = 0; j < q; j++)
    {
        cin >> t[j];
        if(t[j] == 1) cin >> b[j] >> r[j];
        else cin >> s[j] >> c[j];
    }
 
 
    vi ans(q, -1);
 
    vi temp_edge_found(1+m, 0);
 
 
    for(int bl = 0; bl <= (q-1)/rt; bl++)
    {
        int y = rt*bl;
        int z = min(rt*(bl+1)-1, q-1);
 
        // cerr << "current block = " << y << ' ' << z << '\n';
 
        vi mod(1+m);
        for(int j = y; j <= z; j++)
            if(t[j] == 1)
                mod[b[j]] = 1;
 
        vi ops;
        for(int e = 1; e <= m; e++)
            if(!mod[e])
                ops.push_back(e);
 
        for(int j = y; j <= z; j++)
            if(t[j] == 2)
                ops.push_back(-j);
 
        sort(ops.begin(), ops.end(), [] (int d, int f)
        {
            int wd = wt(d), wf = wt(f);
            if(wd != wf) return wd > wf;
            else return d > f;
        });
 
        disjoint_set dsu;
 
 
        for(int o: ops)
        {
            // cerr << "\n\n\n";
            if(o > 0)
            {
                dsu.join(u[o], v[o]);
                // cerr << "general join: " << o << '\n';
            }
            else
            {
                int qr = -o;
                int curr_ct = 0;
 
                // cerr << "answering query : " << qr << '\n';
 
                for(int l = qr-1; l >= y; l--)
                {
                    if(t[l] == 2) continue;
                    if(temp_edge_found[b[l]]) continue;
 
                    temp_edge_found[b[l]] = 1;
 
                    if(r[l] >= c[qr])
                    {
                    // cerr << "query specific join 1: " << b[l] << '\n';
                        dsu.join(u[b[l]], v[b[l]]);
                        curr_ct++;
                    }
                }
 
                for(int l = qr+1; l <= z; l++)
                {
                    // cerr << "l = " << l << '\n';
                    if(t[l] == 2) continue;
                    if(temp_edge_found[b[l]]) continue;
                    // cerr << "success!\n";
 
                    temp_edge_found[b[l]] = 1;
 
                    // cerr << b[l] << " > " << w[b[l]] << ' ' << c[qr] << '\n';
                    if(w[b[l]] >= c[qr])
                    {
                    // cerr << "query specific join 2: " << b[l] << '\n';
                        dsu.join(u[b[l]], v[b[l]]);
                        curr_ct++;
                    }
                }
 
                ans[qr] = dsu.reach(s[qr]);
 
 
                for(int ct = 0; ct < curr_ct; ct++)
                {
 
                    // cerr << "rollback\n";
                        dsu.rollback();
                }
 
                for(int l = y; l <= z; l++)
                {
                    if(t[l] == 1)
                    {
                        temp_edge_found[b[l]] = 0;
                    }
                }
 
 
            }
        }
 
        for(int l = y; l <= z; l++)
        {
            if(t[l] == 1)
            {
                w[b[l]] = r[l];
            }
        }
 
 
    }
 
    for(int j = 0; j < q; j++)
        if(t[j] == 2)
            cout << ans[j] << '\n';
}

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