Submission #922244

#	Time	Username	Problem	Language	Result	Execution time	Memory
922244		bohicob493	Bridges (APIO19_bridges)	C++17	100 / 100	1556 ms	36092 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 5e4 + 1, SQ = 900;

int wei[MAXN * 2], par[MAXN], sz[MAXN];
PII edg[MAXN * 2];
bool marke[MAXN * 2];
struct Query {
    int t, x, y;
} quer[MAXN * 2];
VI bucket[MAXN * 4];
int ans[MAXN * 2];
VI N[MAXN];
bool mark[MAXN];
int lstw[MAXN * 2];

int gp(int v){
    return par[v] == v ? v : par[v] = gp(par[v]);
}

void merge(int u, int v){
    u = gp(u), v = gp(v);
    if (u == v) return;
    par[u] = v;
    sz[v] += sz[u];
}

int sigma, globpnt;
int trash[MAXN];
int dfsarr[MAXN];
void dfs(int v){
    /*
    trash[++globpnt] = v;
    mark[v] = 1;
    sigma += sz[v];
    for (int u : N[v]){
        if (!mark[u]) dfs(u);
    }
    */
    int curpnt = 1, szz = 1;
    dfsarr[1] = v;
    mark[v] = 1;
    while (curpnt <= szz){
        int u = dfsarr[curpnt];
        trash[++globpnt] = u;
        sigma += sz[u];
        for (int w : N[u]){
            if (!mark[w]){
                dfsarr[++szz] = w;
                mark[w] = 1;
            }
        }
        curpnt++;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    VI cmpr;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v >> wei[i];
        edg[i] = MP(u, v);
        cmpr.PB(wei[i]);
    }
    int q; cin >> q;
    for (int i = 0; i < q; i++){
        cin >> quer[i].t >> quer[i].x >> quer[i].y;
        cmpr.PB(quer[i].y);
    }
    sort(all(cmpr));
    cmpr.resize(unique(all(cmpr)) - cmpr.begin());
    for (int i = 1; i <= m; i++){
        wei[i] = lower_bound(all(cmpr), wei[i]) - cmpr.begin() + 1;
        lstw[i] = wei[i];
    }
    for (int i = 0; i < q; i++){
        quer[i].y = lower_bound(all(cmpr), quer[i].y) - cmpr.begin() + 1;
    }
    int mxwei = cmpr.size();
    for (int i = 0; i < q; i++){
        if (i % SQ) continue;
        //cout << "#1" << endl;
        vector<PII> procs;
        VI upds;
        for (int j = i; j < min(i + SQ, q); j++){
            if (quer[j].t == 1){
                marke[quer[j].x] = 1;
                upds.PB(j);
            } else {
                procs.PB(MP(-quer[j].y, j));
            }
        }
        //for (int j = 1; j <= m; j++) cout << marke[j];
        //cout << endl;
        for (int j = 1; j <= m; j++){
            if (marke[j]) continue;
            bucket[wei[j]].PB(j);
            //cout << "added " << j << ' ' << wei[j] << ' ' << " to bucket" << endl;
        }
        fill(sz, sz + n + 1, 1);
        iota(par, par + n + 1, 0);
        sort(all(procs));
        int pnt = mxwei;
        for (auto [tmpw, id] : procs){
            int W = -tmpw;
            //cout << "proces : ";
            //cout << id+1 << ' ' << W << endl;
            while (pnt >= W){
                for (int E : bucket[pnt]){
                    merge(edg[E].first, edg[E].second);
                    //cout << "merged " << edg[E].first << ' ' << edg[E].second << endl;
                }
                pnt--;
            }
            for (int j : upds){
                if (j > id) break;
                lstw[quer[j].x] = quer[j].y;
            }
            for (int j : upds){
                if (lstw[quer[j].x] && lstw[quer[j].x] >= W){
                    auto [u, v] = edg[quer[j].x];
                    u = gp(u);
                    v = gp(v);
                    N[u].PB(v);
                    N[v].PB(u);
                    //cout << "add edg " << u << ' ' << v << endl;
                }
            }
            sigma = 0;
            globpnt = 0;
            dfs(gp(quer[id].x));
            ans[id] = sigma;
            for (int j = 1; j <= globpnt; j++) mark[trash[j]] = 0;
            ////////////////////////////////////////////
            for (int j : upds){
                if (lstw[quer[j].x] && lstw[quer[j].x] >= W){
                    auto [u, v] = edg[quer[j].x];
                    u = gp(u);
                    v = gp(v);
                    N[u].pop_back();
                    N[v].pop_back();
                    //cout << "rmv edg " << u << ' ' << v << endl;
                }
            }
            for (int j : upds){
                if (j > id) break;
                lstw[quer[j].x] = wei[quer[j].x];
            }
        }
        for (int j = 1; j <= m; j++){
            if (marke[j]) continue;
            bucket[wei[j]].clear();
        }
        for (int j = i; j < min(i + SQ, q); j++){
            if (quer[j].t == 1){
                marke[quer[j].x] = 0;
                lstw[quer[j].x] = wei[quer[j].x] = quer[j].y;
            }
        }
    }
    for (int i = 0; i < q; i++){
        if (ans[i]) cout << ans[i] << endl;
    }
    return 0;
}

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