Submission #1118015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118015		gdragon	Bridges (APIO19_bridges)	C++17	27 / 100	3068 ms	9916 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 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 solve() {
    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;
}
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:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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