Submission #600378

#	Time	Username	Problem	Language	Result	Execution time	Memory
600378		Ozy	Bridges (APIO19_bridges)	C++17	100 / 100	2707 ms	413036 KiB

bridges

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

#define MAX 100000

#define w first
#define ini second.first
#define fin second.second
#define tipo first
#define x second.first
#define y second.second

#define C 1500

lli n,m,q,a,b,c,cont,l,r;
lli bfijos[MAX+2], respuestas[MAX + 2];
pair<lli, pair<lli,lli> > puentes[MAX+2];
vector< pair<lli, pair<lli,lli> > > querys;
vector<lli> porUnir[MAX + 2];
lli dsu[MAX + 2], tam[MAX + 2];
stack<lli> stackdsu;

lli sube(lli a){
    while (a != dsu[a]) a = dsu[a];
    return a;
}

void une(lli a, lli b, bool registra){
    a = sube(a);
    b = sube(b);
    if (a == b) return;
    if (tam[a] > tam[b]) swap(a, b);
    dsu[a] = b;
    tam[b] += tam[a];
    if (registra) stackdsu.push(a);
}

void separa(lli a){
    tam[dsu[a]] -= tam[a];
    dsu[a] = a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    rep(i,1,m) {
        cin >> a >> b >> c;
        puentes[i] = {c,{a,b}};
    }

    cin >> q;
    cont = 1;

    querys.push_back({0,{0,0}});
    rep(Q,1,q) {
        cin >> a >> b >> c;
        querys.push_back({a,{b,c}});
    }

    l = 1;
    r = min(l + C, q);
    while(l <= q){

        //preparo la cubeta
        fill(bfijos, bfijos+m+2, 1);
        vector<lli> fijos, cambian, procesar;

        // primera vuelta
        rep(i, l, r) if (querys[i].tipo == 1) bfijos[querys[i].x] = 0;
        rep(i, 1, m) if(bfijos[i]) fijos.push_back(i); else cambian.push_back(i);

        // segunda vuelta
        rep(i, l, r){
            if (querys[i].tipo == 1) puentes[querys[i].x].w = querys[i].y;
            else {
                for(auto puente : cambian){
                    if (puentes[puente].w >= querys[i].y) porUnir[i].push_back(puente);
                }
                procesar.push_back(i);
            }
        }

        //proceso la cubeta
        sort(fijos.begin(), fijos.end(), [&](lli a, lli b){return puentes[a].w > puentes[b].w;});
        sort(procesar.begin(), procesar.end(), [&](lli a, lli b){return querys[a].y > querys[b].y;});

        // inicializa dsu
        fill(tam + 1, tam + n + 1, 1);
        iota(dsu, dsu + n + 1, 0);

        a = b = 0;
        while (b < procesar.size()){
            lli idq = procesar[b];

            while (a < fijos.size() && puentes[fijos[a]].w >= querys[idq].y){
                une(puentes[fijos[a]].ini, puentes[fijos[a]].fin, false);
                ++a;
            }

            for(auto var : porUnir[idq]) une(puentes[var].ini, puentes[var].fin, true);

            lli tmp = sube(querys[idq].x);
            respuestas[idq] = tam[tmp];

            while(!stackdsu.empty()){
                separa(stackdsu.top());
                stackdsu.pop();
            }
            b++;
        }

        l = r + 1;
        r = min(l + C, q);
    }

    rep(i, 1, q){
        if (querys[i].tipo == 2) cout << respuestas[i] << "\n";
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:101:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         while (b < procesar.size()){
      |                ~~^~~~~~~~~~~~~~~~~
bridges.cpp:104:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while (a < fijos.size() && puentes[fijos[a]].w >= querys[idq].y){
      |                    ~~^~~~~~~~~~~~~~

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