Submission #1278771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278771		janson0109	Bridges (APIO19_bridges)	C++20	13 / 100	3096 ms	22608 KiB

bridges

#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

ll find(ll x, vector<ll> &p) {return p[x] == x ? x : (p[x] = find(p[x], p));}
bool unite(ll x, ll y, vector<ll> &p, vector<ll> &s) {
    ll xr = find(x, p);
    ll yr = find(y, p);
    if(xr == yr) return false;
    if(s[xr] < s[yr]) swap(xr,yr);
    s[xr]+=s[yr];
    p[yr]=xr;
    return true;
}

int main() {
	lol
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> e;
    for(ll i=0; i<m; i++) {
        ll u, v, d;
        cin >> u >> v >> d;
        u--;v--;
        e.push_back({d, u, v});
    }
    ll q; cin >> q;
    vector<vector<ll>> qu(q, vector<ll>(3));
    for(ll i=0; i<q; i++) for(ll j=0; j<3; j++) cin >> qu[i][j];
    ll b = sqrtl(q);
    for(ll t=0; t < q; t+=b) {
        ll c = min(b, q-t);
        vector<bool> ch(m,0);
        for(ll i=0; i<c; i++) if(qu[t+i][0] == 1) ch[qu[t+i][1] - 1] = 1;
        vector<ll> mod;
        for(ll i=0; i<m; i++) if(ch[i]) mod.push_back(i);
        ll k = mod.size(); map<ll,ll> modm;
        vector<ll> nd(k);
        for(ll i=0; i<k; i++) {
            nd[i] = e[mod[i]][0];
            modm[mod[i]] = i;
        }
        vector<vector<ll>> ndm(c);
        for(ll i=0; i<c; i++) {
            if(qu[t+i][0] == 1) nd[modm[qu[t+i][1] - 1]] = qu[t+i][2];
            else ndm[i] = nd;
        }

        vector<vector<ll>> qus;
        for(ll i=0; i<c; i++) if(qu[t+i][0] == 2) qus.push_back({qu[t+i][2], qu[t+i][1]-1, i});
        sort(qus.begin(), qus.end(), greater<vector<ll>>());
        set<vector<ll>> uc;
        for(ll i=0; i<m; i++) if(!ch[i]) uc.insert(e[i]);

        vector<ll> p(n), s(n,1);
        iota(p.begin(), p.end(), 0);
        vector<ll> ans(c, -1);
        auto it = uc.rbegin();
        for(auto & quer : qus) {
            while(it != uc.rend() && quer[0] <= (*it)[0]) {
                unite((*it)[1], (*it)[2], p, s);
                it++;
            }
            vector<ll> p2 = p, s2 = s;
            for(ll j=0; j<k; j++) if(quer[0] <= ndm[quer[2]][j]) unite(e[mod[j]][1], e[mod[j]][2], p2,s2);
            ans[quer[2]] = s2[find(quer[1], p2)];
        }
        for(ll i=0; i<c; i++) if(qu[t+i][0] == 1) e[qu[t+i][1] - 1][0] = qu[t+i][2];
        for(ll i=0; i<c; i++) if(ans[i] != -1) cout << ans[i] << '\n';
    }
    
    
    return 0;
}

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