Submission #869024

#	Time	Username	Problem	Language	Result	Execution time	Memory
869024		TS_2392	Bridges (APIO19_bridges)	C++14	100 / 100	1593 ms	215524 KiB

bridges

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
// using namespace __gnu_pbds;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL            cout << '\n'
#define dbg(x)        cout << #x << " = " << (x) << ' '
#define dbgp(x)       cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}

#define epl           emplace
#define pb            push_back
#define eb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

#define sqr(x)        ((x) * (x))
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define lwb           lower_bound
#define upb           upper_bound

#define clz           __builtin_clzll // or __builtin_clz
#define ctz           __builtin_ctzll // or __builtin_ctz
#define pct           __builtin_popcountll // or __builtin_popcount

typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}

// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 1e5 + 3, bz = 1000;
int n, m, q, pr[N], res[N];
int node_a[N], node_b[N], w[N];
int type[N], x[N], y[N];
bool changed[N];
vector<int> to_unite[N];
stack<pii> stk;
int find_set(int u){
    return pr[u] < 0 ? u : find_set(pr[u]);
}
void unite(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(pr[u] > pr[v]) swap(u, v);
    stk.push({u, pr[u]});
    stk.push({v, pr[v]});
    pr[u] += pr[v]; pr[v] = u;
}
void rollback(int sz){
    while(stk.size() > sz){
        pii x = stk.top();
        pr[x.fi] = x.se; stk.pop();
    }
}
void TS_2392(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> node_a[i] >> node_b[i] >> w[i];
    }
    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> type[i] >> x[i] >> y[i];
    }
    for(int l = 1; l <= q; l += bz){
        int r = min(l + bz - 1, q);
        memset(pr, 255, sizeof(pr));
        memset(changed, 0, sizeof(changed));
        vector<int> upd, ask, remain;
        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                changed[x[i]] = true;
                upd.eb(i);
            }
            else ask.eb(i);
        }
        for(int i = 1; i <= m; ++i) if(!changed[i]){
            remain.eb(i);
        }
        sort(all(remain), [&](const int &i1, const int &i2){
            return w[i1] > w[i2];
        });
        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                w[x[i]] = y[i];
            }
            else{
                for(int &j : upd) if(w[x[j]] >= y[i]){
                    to_unite[i].eb(x[j]);
                }
            }
        }
        sort(all(ask), [&](const int &i1, const int &i2){
            return y[i1] > y[i2];
        });
        int ptr = 0;
        for(int &i : ask){
            while(ptr < remain.size() && y[i] <= w[remain[ptr]]){
                unite(node_a[remain[ptr]], node_b[remain[ptr]]);
                ++ptr;
            }
            int sz = stk.size();
            for(int &j : to_unite[i]){
                unite(node_a[j], node_b[j]);
            }
            res[i] = -pr[find_set(x[i])];
            rollback(sz);
        }
    }
    for(int i = 1; i <= q; ++i) if(res[i] > 0){
        cout << res[i] << '\n';
    }
}
int main(){
    SPEED; fileIO("text");
    int numtest = 1; //cin >> numtest;
    for(int itest = 1; itest <= numtest; ++itest){
        // cout << "Case #" << itest << ": ";
        TS_2392(); //cout << '\n';
    }
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * small cases, special cases (n = 1 ???)
 * do something instead of nothing: code bruteforce
 * WRITE STUFF DOWN and STAY ORGANIZED
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:72: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]
   72 |     while(stk.size() > sz){
      |           ~~~~~~~~~~~^~~~
bridges.cpp: In function 'void TS_2392()':
bridges.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             while(ptr < remain.size() && y[i] <= w[remain[ptr]]){
      |                   ~~~~^~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:12: note: in expansion of macro 'fileIO'
  136 |     SPEED; fileIO("text");
      |            ^~~~~~
bridges.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:12: note: in expansion of macro 'fileIO'
  136 |     SPEED; fileIO("text");
      |            ^~~~~~

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