Submission #1281758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281758		khoile08	Bridges (APIO19_bridges)	C++20	59 / 100	3093 ms	4200 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define db double
#define ii pair<int,int>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int N = 5e4 + 2;
const int M = 1e5 + 2;
const int BL = 320;

const int mod = 1e9 + 7;

int add(int a, int b) {return (a + b) % mod;}
int sub(int a, int b) {return (((a - b) % mod) + mod) % mod;}
int mul(int a, int b) {return 1LL * a * b % mod;}

int n, m, q;
int ans[M];

struct Edge {
    int u, v, w;
} e[M];

struct Query {
    int t, a, b;
} qu[M];

struct Dsu {
    int root[N], sze[N];
    stack<int> st;

    void init() {
        FOR(i, 1, n) {
            root[i] = i;
            sze[i] = 1;
        }
        while(st.size()) st.pop();
    }

    int anc(int u) {
        while(u != root[u]) u = root[u];
        return u;
    }

    void join(int u, int v) {
        u = anc(u); v = anc(v);
        if(u == v) return;
        if(sze[u] < sze[v]) swap(u, v);
        st.push(v);
        root[v] = u;
        sze[u] += sze[v];
    }

    void rollback(int x) {
        while(st.size() > x) {
            int v = st.top();
            st.pop();
            sze[root[v]] -= sze[v];
            root[v] = v;
        }
    }
} dsu;

vector<int> save, change, ask;
vector<int> req[BL + 2];
bool keep[M];

void KhoiLe() {
    for(int query = 1; query <= q; query += BL) {
        int l = query, r = (query + BL - 1 <= q ? query + BL - 1 : q);

        FOR(i, 1, m) keep[i] = 1;
        save.clear(); change.clear(); ask.clear();
        dsu.init();

        FOR(i, l, r) {
            if(qu[i].t == 1) keep[qu[i].a] = 0;
            else ask.pb(i);
        }
        FOR(i, 1, m) {
            if(keep[i]) save.pb(i);
            else change.pb(i);
        }

        sort(save.begin(), save.end(), [&](int i, int j) {return e[i].w > e[j].w;});
        sort(ask.begin(), ask.end(), [&](int i, int j) {return qu[i].b > qu[j].b;});

        FOR(i, l, r) {
            if(qu[i].t == 1) e[qu[i].a].w = qu[i].b;
            else {
                for(int id : change) {
                    if(e[id].w >= qu[i].b) req[i - l].pb(id);
                }
            }
        }

//        cout << "ASK: ";
//        for(int id : ask) cout << id << ' ';
//        cout << '\n';
//
//        cout << "SAVE: ";
//        for(int id : save) cout << id << ' ';
//        cout << '\n';
//
//        cout << "REQ: ";
//        for(int id : req[0]) cout << id << ' ';
//        cout << '\n';

        int p = 0;
        for(int id : ask) {
//            cout << e[p].w << ' ' << qu[id].b << '\n';
            while(p < save.size() && e[save[p]].w >= qu[id].b) {
                dsu.join(e[save[p]].u, e[save[p]].v);
                p++;
//                cout << "c" << '\n';
            }
//            cout << "P: " << p << '\n';
            int prev = dsu.st.size();
            for(int x : req[id - l]) dsu.join(e[x].u, e[x].v);
            req[id - l].clear();
            ans[id] = dsu.sze[dsu.anc(qu[id].a)];
            dsu.rollback(prev);
        }
    }
    FOR(i, 1, q) if(qu[i].t == 2) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
//        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;

    while(test--) {
        cin >> n >> m;
        FOR(i, 1, m) cin >> e[i].u >> e[i].v >> e[i].w;
        cin >> q;
        FOR(i, 1, q) cin >> qu[i].t >> qu[i].a >> qu[i].b;
        KhoiLe();
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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