Submission #638920

#	Time	Username	Problem	Language	Result	Execution time	Memory
638920		BackNoob	Bridges (APIO19_bridges)	C++14	100 / 100	2472 ms	10380 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
/*
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
*/

const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
const int block = 1000;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

struct DSU{
    int n;
    vector<int> lab;
    vector<pair<int*, int>> trace;

    DSU(){}
    DSU(int _n)
    {
        n = _n;
        lab.resize(n + 7, -1);
    }

    int root(int u) {return lab[u] < 0 ? u : root(lab[u]);}

    void rollback(int idx)
    {
        for(; sz(trace) > idx; trace.pop_back()) {
            *trace.back().fi = trace.back().se;
        }
    }
    void change(int &a, int b)
    {
        trace.pb({&a, a});
        a = b;
    }

    bool union_root(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        change(lab[u], lab[v] + lab[u]);
        change(lab[v], u);
        return true;
    }
    int getnow()
    {
        return sz(trace);
    }
} dsu;

struct EDGE{
    int u, v, w;
} ed[mxN];

struct QUERY{
    int op, x, y;
} query[mxN];

struct item{
    int x, y, idx;
    bool operator<(const item &a) const {
        return y > a.y;
    }
};

bool cmp(int &a, int &b)
{
    return ed[a].w > ed[b].w;
}

int n;
int m;
int q;
int neww[mxN];
int ans[mxN];
bool changed[mxN];


void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ed[i] = {u, v, c};
    }
    cin >> q;
    for(int i = 1; i <= q; i++) cin >> query[i].op >> query[i].x >> query[i].y;

    dsu = DSU(n);
    for(int lef = 1; lef <= q; lef += block) {
        int rig = min(q, lef + block - 1);

        vector<item> calc;
        for(int j = lef; j <= rig; j++) {
            if(query[j].op == 1) {
                changed[query[j].x] = true;
            }
            else {
                calc.pb({query[j].x, query[j].y, j});
            }
        }

        sort(all(calc));

        vector<int> upd;
        vector<int> spec;
        for(int j = 1; j <= m; j++) {
            if(changed[j] == false) upd.pb(j);
            else spec.pb(j);
            changed[j] = false;
        }

        sort(all(upd), cmp);

        dsu.rollback(0);
        int p = 0;
        for(auto it : calc) {
            while(p < sz(upd) && ed[upd[p]].w >= it.y) {
                dsu.union_root(ed[upd[p]].u, ed[upd[p]].v);
                ++p;
            }
            int keep = dsu.getnow();
            for(auto jt : spec) neww[jt] = ed[jt].w;
            for(int j = lef; j <= it.idx; j++) {
                if(query[j].op == 1) {
                    neww[query[j].x] = query[j].y;
                }
            }
            for(auto jt : spec) if(neww[jt] >= it.y) dsu.union_root(ed[jt].u, ed[jt].v);
            ans[it.idx] = -dsu.lab[dsu.root(it.x)];
            dsu.rollback(keep);
        }

        for(int j = lef; j <= rig; j++) {
            if(query[j].op == 1) {
                ed[query[j].x].w = query[j].y;
            }
        }
    }

    for(int i = 1; i <= q; i++) if(query[i].op == 2) cout << ans[i] << endl;

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

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