Submission #1158861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158861		heeheeheehaaw	Swapping Cities (APIO20_swap)	C++20	37 / 100	2100 ms	302556 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"

using namespace std;

typedef long double ld;
typedef long long ll;
const int bucketsize = 2000;
const int obsize = 200000 / bucketsize;
//#define int long long

struct DSU
{
    vector<int> deg, parent, siz;
    vector<int> cdeg, cparent, csiz;
    vector<char> maxdeg, cmaxdeg;
    vector<int> modif;
    vector<bool> apare, earb, cearb;

    void init(int n)
    {
        deg.resize(n);
        siz.resize(n);
        parent.resize(n);
        maxdeg.resize(n);
        apare.resize(n);
        earb.resize(n);
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            siz[i] = 1;
            maxdeg[i] = deg[i] = 0;
            apare[i] = 0;
            earb[i] = 1;
        }
    }

    void seteaza()
    {
        cdeg = deg;
        cmaxdeg = maxdeg;
        cparent = parent;
        csiz = siz;
        cearb = earb;
        for (auto u : modif)
            apare[u] = false;
        modif.clear();
    }

    void reset()
    {
        //cerr<<"resetez\n"<<modif.size()<<"\n\n";
        for (auto u : modif)
        {
            apare[u] = false;
            parent[u] = cparent[u];
            siz[u] = csiz[u];
            deg[u] = cdeg[u];
            maxdeg[u] = cmaxdeg[u];
            earb[u] = cearb[u];
            //cerr<<" dupa resetare siz "<<u<<" -> "<<siz[u]<<'\n';
        }

        modif.clear();
    }

    int cauta(int u)
    {
        if (u == parent[u])
            return u;
        if (apare[u] == 0) apare[u] = 1, modif.push_back(u);
        return parent[u] = cauta(parent[u]);
    }

    void unite(int u, int v)
    {
        deg[u]++;
        deg[v]++;
        if (apare[u] == 0) apare[u] = 1, modif.push_back(u);
        if (apare[v] == 0) apare[v] = 1, modif.push_back(v);

        int cu = cauta(u);
        int cv = cauta(v);
        maxdeg[cu] = max(maxdeg[cu], (char)min(3, deg[u]));
        maxdeg[cv] = max(maxdeg[cv], (char)min(3, deg[v]));
        u = cu;
        v = cv;
        if (apare[cu] == 0) apare[cu] = 1, modif.push_back(cu);
        if (apare[cv] == 0) apare[cv] = 1, modif.push_back(cv);

        if (u == v)
        {
            earb[u] = false;
            return;
        }

        if (siz[u] > siz[v])
            swap(u, v);
        parent[u] = v;
        siz[v] += siz[u];
        maxdeg[v] = max(maxdeg[v], maxdeg[u]);
        if (earb[u] == false) earb[v] = false;
    }

};

struct muchie
{
    int u, v, c;
};

DSU dsu[obsize + 5];
//DSU dsu2[obsize + 5];
DSU aux;

int n, m;
vector<muchie> muc;
int cntbuc = 0;

void init(int N, int M, std::vector<int> u, std::vector<int> v, std::vector<int> w)
{
    n = N, m = M;
    for (int i = 0; i < m; i++)
    {
        muc.push_back({u[i], v[i], w[i]});
    }

    sort(muc.begin(), muc.end(), [](muchie a, muchie b)
    {
       return a.c < b.c;
    });

    aux.init(n);
    dsu[0] = aux;
    dsu[0].seteaza();
    //dsu2[0] = dsu[0];
    for (int i = 1; i <= m; i++)
    {
        aux.unite(muc[i - 1].u, muc[i - 1].v);
        if (i % bucketsize == 0)
        {
            dsu[++cntbuc] = aux;
            dsu[cntbuc].seteaza();
            //dsu2[cntbuc] = dsu[cntbuc];
        }
    }
}

int getMinimumFuelCapacity(int uu, int vv)
{
    int fbucket = 0;
    //cout<<obsize<<endl;
    for (int i = 1; i <= cntbuc; i++)
    {
        int u = dsu[i].cauta(uu);
        int v = dsu[i].cauta(vv);
        fbucket = i;
        if (u == v && ((int)dsu[i].maxdeg[u] > 2 || !dsu[i].earb[u]))
        {
            fbucket--;
            break;
        }
    }

    //assert(fbucket == 0);
    int fmuc = fbucket * bucketsize + 1;
    int lim = min(m, fmuc + bucketsize);
    for (int i = fmuc; i <= lim; i++)
    {
        dsu[fbucket].unite(muc[i - 1].u, muc[i - 1].v);

        int u = dsu[fbucket].cauta(uu);
        int v = dsu[fbucket].cauta(vv);

        if (u == v && ((int)dsu[fbucket].maxdeg[u] > 2 || !dsu[fbucket].earb[u]))
        {
            //dsu[fbucket].reset();
            //cout<<i<<" "<<u<<" "<<v<<" "<<(int)dsu[fbucket].maxdeg[u]<<" "<<dsu[fbucket].earb[u]<<" "<<fbucket<<'\n';
            dsu[fbucket].reset();
            return muc[i - 1].c;
        }
    }

    dsu[fbucket].reset();
    return -1;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27