Submission #1118194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118194		gdragon	Bridges (APIO19_bridges)	C++17	43 / 100	3068 ms	10688 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;
    }
};
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;
    DSU(int _n = 0) {
        n = _n;
        par.assign(n + 2, -1);
    }
    void init() {
        fill(ALL(par), -1);
    }
    int root(int v) {
        return par[v] < 0 ? v : (par[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);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
} dsu;
struct Query {
    int type, s, w;
} 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;
}
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;
        }
    }
}
void solve() {
    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:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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