Submission #1267344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267344		CrabCNH	Bridges (APIO19_bridges)	C++20	100 / 100	1409 ms	9288 KiB

bridges

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 1e5 + 5;
const ll inf = 1e18 + 7;
const int mod = 1e9 + 7;

struct Edge {
    int u, v, w, id;
};

struct Back {
    int u, v, szU;
};

bool cmp (Edge A, Edge B) {
    return A.w > B.w;
}

bool cmpT (Edge A, Edge B) {
    return A.id < B.id;
}

int maxSz;
int n, m;
Edge ed[maxN];
vector <pii> change[maxN];
int res[maxN], par[maxN], sz[maxN];
vector <Back> hist;
int ys[maxN], vis[maxN];

inline void init () {
    for (int i = 1; i <= n; i ++) {
        par[i] = i;
        sz[i] = 1;
    }
    hist.clear ();
}

int getRoot (int u) {
    if (par[u] == u) {
        return u;
    }
    return (getRoot (par[u]));
}

inline void merge (int u, int v) {
    u = getRoot (u);
    v = getRoot (v);
    if (u == v) {
        return;
    }
    if (sz[u] < sz[v]) {
        swap (u, v);
    }
    hist.push_back ({u, v, sz[u]});
    par[v] = u;
    sz[u] += sz[v];
}

inline void rollBack (int p) {
    while (sz (hist) > p) {
        auto [u, v, szU] = hist.back ();
        hist.pop_back ();
        par[v] = v;
        sz[u] = szU;
    }
}

int getVal (int id, int t) {
    if (sz (change[id]) == 0) {
        return ed[ys[id]].w;
    }
    int val = ed[ys[id]].w;
    int l = 0, r = sz (change[id]) - 1, pos = -1;
    while (true) {
        if (l > r) {
            break;
        }
        int mid = (l + r) >> 1;
        if (change[id][mid].se <= t) {
            pos = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    if (pos != -1) {
        val = change[id][pos].fi;
    }
    return val;
}

vector <Edge> o2;

inline void calc () {
    init ();
    for (int i = 1; i <= m; i ++) {
        vis[i] = 0;
    }
    vector <int> dyn;
    for (int i = 1; i <= m; i ++) {
        if (sz (change[i])) {
            vis[i] = -1;
            dyn.push_back (i);
        }
    }
    sort (all (o2), cmp);
    int it = 1;
    for (int i = 0; i < sz (o2); i ++) {
        while (it <= m && ed[it].w >= o2[i].w) {
            if (!vis[ed[it].id]) {
                merge (ed[it].u, ed[it].v);
            }
            it ++;
        }
        int pos = sz (hist);
        for (int id : dyn) {
            int val = getVal (id, o2[i].id);
            if (val >= o2[i].w) {
                int idx = ys[id];
                merge (ed[idx].u, ed[idx].v);
            }
        }
        res[o2[i].id] = sz[getRoot (o2[i].u)];
        rollBack (pos);
    }
    for (int i = 1; i <= m; i ++) {
        if (sz (change[i])) {
            ed[ys[i]].w = change[i].back ().fi;
            change[i].clear ();
            vis[i] = 0;
        }
    }
    sort (ed + 1, ed + m + 1, cmp);
    for (int i = 1; i <= m; i ++) {
        ys[ed[i].id] = i;
    }
    o2.clear ();
}

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, i};
    }
    sort (ed + 1, ed + m + 1, cmp);
    for (int i = 1; i <= m; i ++) {
        ys[ed[i].id] = i;
    }
    int q;
    cin >> q;
    maxSz = 1000;
    for (int i = 1; i <= q; i ++) {
        int t;
        cin >> t;
        if (i % maxSz == 0) {
            calc ();
        }
        if (t == 1) {
            int b, r;
            cin >> b >> r;
            change[b].push_back ({r, i});
        }
        else {
            int s, w;
            cin >> s >> w;
            o2.push_back ({s, s, w, i});
        }
    }
    calc ();
    for (int i = 1; i <= q; i ++) {
        if (res[i]) {
            cout << res[i] << '\n';
        }
    }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    while (t --) {
        solve ();
    } 
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:203:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:204:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         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