Submission #535960

#	Time	Username	Problem	Language	Result	Execution time	Memory
535960		Evang	Bridges (APIO19_bridges)	C++17	100 / 100	1923 ms	131244 KiB

bridges

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

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int bsz = 1000;
const int M = 1e5+5;
const int Q = M;
int n, m, q, t[Q], x[Q], y[Q], ans[Q];
struct edge {
    int v, u, w;
} e[M];
vi to_join[Q];

struct dsu {
    vi lk, sz, un;
    dsu(int n){
        lk.resize(n);
        sz.resize(n);
        iota(all(lk), 0);
        fill(all(sz), 1);
    }
    int root(int a){
        while(a^lk[a])
            a = lk[a];
        return a;
    }
    void join(int a, int b){
        a = root(a);
        b = root(b);
        if(a==b)
            return;

        if(sz[a]<sz[b])
            swap(a, b);

        un.pb(b);
        lk[b] = a;
        sz[a] += sz[b];
    }
    void undo(){
        int b = un.back();
        sz[lk[b]] -= sz[b];
        lk[b] = b;
        un.pop_back();
    }
    void undo(int x){
        while(ssize(un)>x)
            undo();
    }
};

struct bset {
    bitset<M> b;
    vi op;
    void set(int i){
        if(b[i])
            return;
        op.pb(i);
        b[i] = 1;
    }
    bool at(int i){
        return b[i];
    }
    void clear(){
        while(!op.empty()){
            b[op.back()] = 0;
            op.pop_back();
        }
    }
} changed, bset;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> e[i].v >> e[i].u >> e[i].w;

    cin >> q;
    for(int i = 0; i < q; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        // if t[i] == 1, then:
        //     bridge x[i] now has weight y[i]
        // else
        //     car with weight y[i] is on node x[i]
    }

    for(int l = 0; l < q; l += bsz){
        int r = min(l + bsz, q);
        changed.clear();
        vi ask, upd;
        for(int i = l; i < r; ++i) {
            if (t[i] == 1) {
                changed.set(x[i]);
                upd.pb(i);
            }else
                ask.pb(i);
        }
        for(int i = l; i < r; ++i){
            if(t[i]==1)
                e[x[i]].w = y[i];
            else {
                to_join[i].clear();
                for (int j: upd)
                    if(e[x[j]].w >= y[i])
                        to_join[i].pb(x[j]);
            }
        }
        sort(all(ask), [](int i, int j){
            return y[i] > y[j];
        });

        vc<edge> unchanged;
        for(int i = 1; i <= m; ++i)
            if(!changed.at(i))
                unchanged.pb(e[i]);
        sort(all(unchanged), [](edge a, edge b){
            return a.w < b.w;
        });

        dsu d(n+1);
        for(int i: ask){
            while(!unchanged.empty()&&unchanged.back().w>=y[i]) {
                d.join(unchanged.back().v, unchanged.back().u);
                unchanged.pop_back();
            }

            int prev_size = ssize(d.un);
            for(int j: to_join[i])
                d.join(e[j].v, e[j].u);
//            bset.clear();
//            for(int k = p; k >= 0; --k) {
//                int j = upd[k];
//                if (!bset.at(x[j])) {
//                    bset.set(x[j]);
//                    if (y[j] >= y[i])
//                        d.join(e[x[j]].v, e[x[j]].u);
//                }
//            }
//
//            for(int k = p+1; k < ssize(upd); ++k) {
//                int j = upd[k];
//                if (!bset.at(x[j]) && e[x[j]].w >= y[i])
//                    d.join(e[x[j]].v, e[x[j]].u);
//            }

            ans[i] = d.sz[d.root(x[i])];

            d.undo(prev_size);
        }

        for(int i: upd)
            e[x[i]].w = y[i];
    }

    for(int i = 0; i < q; ++i)
        if(t[i]==2)
            cout << ans[i] << el;
}

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