Submission #938198

#	Time	Username	Problem	Language	Result	Execution time	Memory
938198		VinhLuu	Bridges (APIO19_bridges)	C++17	14 / 100	2483 ms	10292 KiB

bridges

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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];
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];

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){
                d[a[i]] = b[i];
                c[a[i]] = 1;
                update.pb(i);
            }else get.pb(i);
        }

        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];});
//        for(auto j : re) cout << j << " ";
//        cout << "h\n";
        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 : update){
                if(j <= i){
                    if(d[a[j]] >= b[i]) dsu(X[a[j]], Y[a[j]]);
                }else if(W[a[j]] >= b[i]) dsu(X[a[j]], Y[a[j]]);
            }
            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:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while(ptr < re.size() && W[re[ptr]] >= b[i]){
      |                   ~~~~^~~~~~~~~~~
bridges.cpp:96: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]
   96 |             while(st.size() > tmp) undo();
      |                   ~~~~~~~~~~^~~~~
bridges.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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