Submission #938217

#	Time	Username	Problem	Language	Result	Execution time	Memory
938217		VinhLuu	Bridges (APIO19_bridges)	C++17	100 / 100	2537 ms	72532 KiB

bridges

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const ll oo = 1e18;
const int mod = 1e9 + 7;

int n, m, q, X[N], Y[N], W[N], pa[N], sz[N], T[N], a[N], b[N];
const int block = 500;

int fin(int x){
    return x == pa[x] ? x : fin(pa[x]);
}

stack<tuple<int,int,int,int>> st;

void dsu(int x,int y){
    x = fin(x);
    y = fin(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    st.push({y, pa[y], x, sz[x]});
    pa[y] = x;
    sz[x] += sz[y];
}

void undo(){
    int x, y, z, t; tie(x, y, z, t) = st.top();
    st.pop();
    pa[x] = y;
    sz[z] = t;
}

int c[N], kq[N], d[N];
vector<int> change[N];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> m;
    for(int i = 1; i <= m; i ++) cin >> X[i] >> Y[i] >> W[i];
    cin >> q;
    for(int i = 1; i <= q; i ++) cin >> T[i] >> a[i] >> b[i];

    for(int l = 1; l <= q; l += block){
        int r = min(q, l + block - 1);
        for(int i = 1; i <= max(n, m); i ++) pa[i] = i, sz[i] = 1, c[i] = 0, d[i] = 0;
        vector<int> get, update;
        while(!st.empty()) st.pop();
        for(int i = l; i <= r; i ++){
            if(T[i] == 1){
                c[a[i]] = 1;
                update.pb(i);
            }else get.pb(i);
        }

        for(int i = l; i <= r; i ++){
            if(T[i] == 1){
                W[a[i]] = b[i];
            }else{
                for(auto j : update){
                    if(W[a[j]] >= b[i]) change[i].pb(a[j]);
                }
            }
        }

        sort(get.begin(), get.end(), [] (int x,int y){return b[x] > b[y];});
        vector<int> re;
        for(int i = 1; i <= m; i ++) if(!c[i]) re.pb(i);

        sort(re.begin(), re.end(), [] (int x,int y){return W[x] > W[y];});
        int ptr = 0;
        for(auto i : get){
            while(ptr < re.size() && W[re[ptr]] >= b[i]){
                dsu(X[re[ptr]], Y[re[ptr]]);
                ptr++;
            }
            int tmp = st.size();
            for(auto j : change[i]) dsu(X[j], Y[j]);
            change[i].clear();
            kq[i] = sz[fin(a[i])];
            while(st.size() > tmp) undo();
        }
    }
    for(int i = 1; i <= q; i ++) if(T[i] == 2) cout << kq[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             while(ptr < re.size() && W[re[ptr]] >= b[i]){
      |                   ~~~~^~~~~~~~~~~
bridges.cpp:98:29: warning: comparison of integer expressions of different signedness: 'std::stack<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |             while(st.size() > tmp) undo();
      |                   ~~~~~~~~~~^~~~~
bridges.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         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