Submission #707588

#	Time	Username	Problem	Language	Result	Execution time	Memory
707588		nguyentunglam	Bridges (APIO19_bridges)	C++17	100 / 100	2911 ms	13264 KiB

bridges

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
vector<ii> w[N];
int u[N], v[N];
bool mark[N];
int lab[N], n, m, ans[N];
stack<pair<int, int> > st;
int root(int v) {
    return lab[v] < 0 ? v : root(lab[v]);
}
void join(int u, int v) {
   u = root(u); v = root(v);
   if (u == v) return;
   if (lab[u] > lab[v]) swap(u, v);
   st.push({u, lab[u]});
   st.push({v, lab[v]});
   lab[u] += lab[v];
   lab[v] = u;
}
void rollback(int cnt) {
    while (st.size() > cnt) {
        lab[st.top().fi] = st.top().se;
        st.pop();
    }
}
int getw (int j, int t) {
    int idx = lower_bound(w[j].begin(), w[j].end(), make_pair(t + 1, 0)) - w[j].begin();
    return w[j][idx - 1].se;
}
vector<tuple<int, int, int> > query;
void solve() {
    sort(query.begin(), query.end(), greater<tuple<int, int, int>>());
    vector<int> remain, change;
    for(int j = 1; j <= m; j++) {
        if (!mark[j]) remain.push_back(j);
        else change.push_back(j);
        mark[j] = 0;
    }
    sort(remain.begin(), remain.end(), [] (int x, int y) {
         return w[x].back().se < w[y].back().se;
         });
    for(auto &t : query) {
        int weight, ver, idx;
        tie(weight, ver, idx) = t;
        while (!remain.empty() && w[remain.back()].back().se >= weight) {
            int j = remain.back();
            join(u[j], v[j]);
            remain.pop_back();
        }
        int pre = st.size();
        for(int &j : change) if (getw(j, idx) >= weight) {
            join(u[j], v[j]);
        }
        ans[idx] = -lab[root(ver)];
        rollback(pre);
    }
    fill(lab + 1, lab + n + 1, -1);
    while (!st.empty()) st.pop();
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> m;
    fill(lab + 1, lab + n + 1, -1);
    for(int i = 1; i <= m; i++) {
        int d;
        cin >> u[i] >> v[i] >> d;
        w[i].emplace_back(0, d);
    }
    int q; cin >> q;
    int T = 1000;
    for(int i = 1; i <= q; i++) {
        int type, x, y; cin >> type >> x >> y;
        if (type == 1) {
            w[x].emplace_back(i, y);
            mark[x] = 1;
        }
        else query.push_back({y, x, i});
        if (i % T == 0 || i == q) solve(), query.clear();
    }
    for(int i = 1; i <= q; i++) if (ans[i]) cout << ans[i] << endl;
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:26:22: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     while (st.size() > cnt) {
      |            ~~~~~~~~~~^~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:69:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:70:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:73:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:74:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         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