Submission #126705

#	Time	Username	Problem	Language	Result	Execution time	Memory
126705		keko37	Bridges (APIO19_bridges)	C++14	100 / 100	2626 ms	11300 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int SIZ = 650;

int n, m, q, br, cnt;
int tip[MAXN], qx[MAXN], qv[MAXN];
int a[MAXN], b[MAXN], w[MAXN], sol[MAXN];
int par[MAXN], siz[MAXN], na[MAXN], nb[MAXN], novi[MAXN], bio[MAXN];
bool ok[MAXN];
vector < pair <int, int> > upiti, st, tmp, fin;
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.push_back(make_pair(w[i], i));
    }
    st.push_back(make_pair(0, 0));
    sort(st.begin(), st.end());
    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] == cnt) return;
    bio[x] = cnt;
    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]));
    }
    cnt++;
    br = 0; lim = qv[ind];
    dfs(nadi(qx[ind]));
    sol[ind] = br;
    for (auto e : magic) {
        v[na[e]].clear();
        v[nb[e]].clear();
    }
}

void update () {
    for (auto i : curr) {
        w[qx[i]] = qv[i];
    }
    tmp.clear(); fin.clear();
    for (auto e : magic) tmp.push_back(make_pair(w[e], e));
    sort(tmp.begin(), tmp.end());
    int p = 0;
    for (int i=0; i<tmp.size(); i++) {
        while (p < st.size() && st[p].first <= tmp[i].first) {
            if (ok[st[p].second] == 0) {
                fin.push_back(st[p]);
            }
            p++;
        }
        fin.push_back(tmp[i]);
    }
    for (int i=p; i<st.size(); i++) {
        if (ok[st[i].second] == 0) fin.push_back(st[i]);
    }
    swap(st, fin);
}

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());
    int p = (int)st.size() - 1;
    for (int i = (int)upiti.size()-1; i >= 0; i--) {
        int ind = upiti[i].second;
        //cout << "sad na upitu " << ind << " " << qv[ind] << endl;
        while (st[p].first >= qv[ind]) {
            if (ok[st[p].second] == 0) spoji(a[st[p].second], b[st[p].second]);
            p--;
        }
        //cout << "sad cu ga obradit" << endl;
        obradi_upit(ind);
    }
    update();
    //for (auto par : st) cout << par.first << " " << par.second << endl;
    for (auto i : curr) ok[qx[i]] = 0;
}

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;
}

Compilation message (stderr)

bridges.cpp: In function 'void update()':
bridges.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<tmp.size(); i++) {
                   ~^~~~~~~~~~~
bridges.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (p < st.size() && st[p].first <= tmp[i].first) {
                ~~^~~~~~~~~~~
bridges.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=p; i<st.size(); i++) {
                   ~^~~~~~~~~~

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