제출 #126489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126489		keko37	다리 (APIO19_bridges)	C++14	44 / 100	3029 ms	15232 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int SIZ = 800;

int n, m, q, br;
int tip[MAXN], qx[MAXN], qv[MAXN];
int a[MAXN], b[MAXN], w[MAXN], sol[MAXN];
set < pair <int, int> > st;
set < pair <int, int> > :: iterator it;
int par[MAXN], siz[MAXN], na[MAXN], nb[MAXN], novi[MAXN], bio[MAXN];
bool ok[MAXN];
vector < pair <int, int> > upiti;
vector <int> curr, magic, visited;
vector <pair <int, int> > v[MAXN];

void load () {
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        cin >> a[i] >> b[i] >> w[i];
        st.insert(make_pair(w[i], i));
    }
    st.insert(make_pair(0, 0));
    cin >> q;
    for (int i=1; i<=q; i++) {
        cin >> tip[i] >> qx[i] >> qv[i];
    }
}

int nadi (int x) {
    if (x == par[x]) return x;
    return par[x] = nadi(par[x]);
}

void spoji (int x, int y) {
    x = nadi(x); y = nadi(y);
    if (x == y) return;
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
}

int lim;

void dfs (int x) {
    if (bio[x]) return;
    bio[x] = 1;
    visited.push_back(x);
    br += siz[x];
    for (auto sus : v[x]) {
        if (sus.second >= lim) dfs(sus.first);
    }
}

void obradi_upit (int ind) {
    for (auto e : magic) novi[e] = w[e];
    for (auto i : curr) {
        if (i >= ind) break;
        novi[qx[i]] = qv[i];
    }
    for (auto e : magic) {
        na[e] = nadi(a[e]);
        nb[e] = nadi(b[e]);
        //cout << "edge " << e << "  " << na[e] << " " << nb[e] << "  " << novi[e] << endl;
    }
    for (auto e : magic) {
        v[na[e]].push_back(make_pair(nb[e], novi[e]));
        v[nb[e]].push_back(make_pair(na[e], novi[e]));
    }
    visited.clear();
    br = 0; lim = qv[ind];
    dfs(nadi(qx[ind]));
    sol[ind] = br;
    for (auto x : visited) {
        bio[x] = 0;
    }
    for (auto e : magic) {
        v[na[e]].clear();
        v[nb[e]].clear();
    }
}

void obradi_bucket (int ll, int rr) {
    for (int i=1; i<=n; i++) {
        par[i] = i; siz[i] = 1;
    }
    upiti.clear(); curr.clear(); magic.clear();
    for (int i = ll; i <= rr; i++) {
        if (tip[i] == 1) {
            ok[qx[i]] = 1;
            magic.push_back(qx[i]);
            curr.push_back(i);
        } else {
            upiti.push_back(make_pair(qv[i], i));
        }
    }
    sort(magic.begin(), magic.end());
    magic.erase(unique(magic.begin(), magic.end()), magic.end());
    sort(upiti.begin(), upiti.end());
    it = st.end(); it--;
    for (int i = (int)upiti.size()-1; i >= 0; i--) {
        int ind = upiti[i].second;
        //cout << "sad na upitu " << ind << " " << qv[ind] << endl;
        while ((it -> first) >= qv[ind]) {
            if (ok[it -> second] == 0) spoji(a[it -> second], b[it -> second]);
            it--;
        }
        //cout << "sad cu ga obradit" << endl;
        obradi_upit(ind);
    }
    for (auto i : curr) {
        ok[qx[i]] = 0;
        st.erase(make_pair(w[qx[i]], qx[i]));
        w[qx[i]] = qv[i];
        st.insert(make_pair(w[qx[i]], qx[i]));
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    load();
    for (int i=1; i<=q; i += SIZ) {
        obradi_bucket(i, min(i + SIZ - 1, q));
    }
    for (int i=1; i<=q; i++) {
        if (tip[i] == 2) cout << sol[i] << '\n';
    }
    return 0;
}

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