Submission #1118295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118295		gdragon	Bridges (APIO19_bridges)	C++17	100 / 100	2840 ms	9924 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
struct Edge {
    int u, v, c;
    Edge(int _u = 0, int _v = 0, int _c = 0) {
        u = _u; v = _v; c = _c;
    }
    bool operator < (const Edge &other) const {
        return c < other.c;
    }
    bool operator > (const Edge &other) const {
        return c < other.c;
    }
};
struct Segtree {
    int n;
    vector<int> st;
    Segtree(int _n = 0) {
        n = _n;
        st.assign(4 * n + 2, INF);
    }
    void update(int id, int l, int r, int p, int c) {
        if (l == r) {
            st[id] = c;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(id<<1, l, mid, p, c);
        else update(id<<1|1, mid + 1, r, p, c);
        st[id] = min(st[id<<1], st[id<<1|1]);
    }
    int getMin(int id, int l, int r, int u, int v) {
        if (u > r || v < l) return INF;
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        return min(getMin(id<<1, l, mid, u, v), getMin(id<<1|1, mid + 1, r, u, v));
    }
    void update(int p, int c) {
        return update(1, 1, n, p, c);
    }
    int getMin(int l, int r) {
        return getMin(1, 1, n, l, r);
    }
} it;
struct DSU {
    int n;
    vector<int> par;
    stack<pair<int, int>> s;
    DSU(int _n = 0) {
        n = _n;
        par.assign(n + 2, -1);
    }
    void init() {
        fill(ALL(par), -1);
        while(!s.empty()) s.pop();
    }
    int root(int v) {
        return par[v] < 0 ? v : (root(par[v]));
    }
    bool join(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[y] < par[x]) swap(x, y);
        s.push({x, par[x]});
        s.push({y, par[y]});
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    void rollback(int sz) {
        while(SZ(s) > sz) {
            auto tmp = s.top(); s.pop();
            par[tmp.fi] = tmp.se;
        }
    }
} dsu;
struct Query {
    int type, s, w;
    int id;
} Q[M];
int n, m, q;
int ans[M];
Edge e[M];
void read() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        e[i] = Edge(u, v, c);
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> Q[i].type >> Q[i].s >> Q[i].w;
        Q[i].id = i;
    }
}
void sub14() {
    dsu = DSU(n);
    vector<pair<int, pair<int, int>>> tmp;
    vector<Edge> fakeE;
    for(int i = 1; i <= q; i++) {
        // cerr << q << ' ' << i << endl;
        if (Q[i].type == 1) {
            // cerr << Q[i].s << ' ' << Q[i].w << endl;
            e[Q[i].s].c = Q[i].w;
            continue;
        }
        fakeE.clear();
        tmp.clear();
        for(int j = 1; j <= m; j++) fakeE.push_back(e[j]);
        sort(ALL(fakeE));
        while(i <= q && Q[i].type == 2) {
            tmp.push_back({Q[i].w, {Q[i].s, i}});
            ++i;
        }
        --i;
        sort(ALL(tmp), greater<pair<int, pair<int, int>>>());
        dsu.init();
        for(auto &j: tmp) {
            while(!fakeE.empty() && fakeE.back().c >= j.fi) {
                auto &z = fakeE.back();
                fakeE.pop_back();
                // cerr << z.u << ' ' << z.v << endl;
                dsu.join(z.u, z.v);
            }
            ans[j.se.se] = -dsu.par[dsu.root(j.se.fi)];
        }
    }
    // cerr << "ok\n";
    for(int i = 1; i <= q; i++) if (Q[i].type == 2) cout << ans[i] << endl;
}
bool check2() {
    bool ok = (m == n - 1);
    for(int i = 1; i < n; i++) ok &= (e[i].u == i && e[i].v == i + 1);
    return ok;
}
void sub2() {
    it = Segtree(n);
    for(int i = 1; i < n; i++) it.update(i, e[i].c);
    for(int i = 1; i <= q; i++) {
        if (Q[i].type == 1) it.update(Q[i].s, Q[i].w);
        else {
            int l = 1, r = Q[i].s - 1;
            int tmp = Q[i].s;
            int res = 0;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if (it.getMin(mid, Q[i].s - 1) >= Q[i].w) {
                    tmp = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            res += (Q[i].s - tmp + 1);
            tmp = Q[i].s;
            l = Q[i].s, r = n - 1;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if (it.getMin(Q[i].s, mid) >= Q[i].w) {
                    tmp = mid + 1;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            res += (tmp - Q[i].s + 1);
            --res;
            cout << res << endl;
        }
    }
}
#define BLOCK 500
bool change[M];
vector<int> toJoin[BLOCK + 1];
void lastSub() {
    dsu = DSU(n);
    vector<int> unchange, ask, upd;
    for(int l = 1; l <= q; l += BLOCK) {
        dsu.init();
        unchange.clear();
        upd.clear();
        ask.clear();
        for(int i = 0; i <= BLOCK; i++) toJoin[i].clear();
        for(int i = 1; i <= m; i++) change[i] = 0;
        int r = min(q, l + BLOCK - 1);
        for(int i = l; i <= r; i++) {
            if (Q[i].type == 1) {
                change[Q[i].s] = 1;
                upd.push_back(i);
            }
            else ask.push_back(i);
        }
        for(int i = 1; i <= m; i++) if (!change[i]) unchange.push_back(i);
        for(int i = l; i <= r; i++) {
            if (Q[i].type == 1) {
                e[Q[i].s].c = Q[i].w;
            }
            else {
                for(int j: upd) if (e[Q[j].s].c >= Q[i].w) {
                    // cerr << Q[j].s << endl;
                    toJoin[i - l].push_back(Q[j].s);
                }
            }
        }
        sort(ALL(unchange), [&](const int &x, const int &y) {return e[x].c > e[y].c; });
        sort(ALL(ask), [&](const int &x, const int &y) {return Q[x].w > Q[y].w;});
        int i = 0;
        for(auto &query: ask) {
            //cerr << "ASK: " << query << endl;
            while(i < SZ(unchange) && e[unchange[i]].c >= Q[query].w) {
                dsu.join(e[unchange[i]].u, e[unchange[i]].v);
                // cerr << "UNCHANGE: " << unchange[i] << ' ' << e[unchange[i]].u << ' ' << e[unchange[i]].v << endl;
                ++i;
            }
            int sz = SZ(dsu.s);
            for(int p: toJoin[query - l]) {
                dsu.join(e[p].u, e[p].v);
                // cerr << p << ' ' << e[p].u << ' ' << e[p].v << endl;
            }
            ans[query] = -dsu.par[dsu.root(Q[query].s)];
            // cerr << "ANS: " << Q[query].s << ' ' << ans[query] << endl;
            dsu.rollback(sz);
        }
    }
    for(int i = 1; i <= q; i++) if (Q[i].type == 2) cout << ans[i] << endl;
}
void solve() {
    lastSub(); return;
    if (check2()) sub2();
    else sub14();
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

// rmq - rmq2d
// hash
// fw - fw2d
// segtree

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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