Submission #808881

#	Time	Username	Problem	Language	Result	Execution time	Memory
808881		pomuchle	Keys (IOI21_keys)	C++17	67 / 100	3070 ms	315796 KiB

keys

#include <vector>
#include <functional>
#define ssize(A) (int(A.size()))
#define FOR(i,a,b) for(auto i=(a);i<=(b);++i)
#define ROF(i,a,b) for(auto i=(a);i>=(b);--i)
#define REP(i,n) for(__typeof(n) i=0; i<(n); ++i)
typedef std::vector <int> vi;
struct kraw{
    int g,t; // gdzie, typ
};
struct rettype{
    int cof;
    bool czybylmin;
};
vi find_reachable(vi r, vi u, vi v, vi c) {
    // r=klucz w wierzch, reszta to kraw
    int n=ssize(r),m=ssize(u);
    int cap;
    if (n>2000)
        cap=30;
    else
        cap=n;
    std::vector <std::vector <vi>> pol(n, std::vector <vi>(cap, vi()));
    vi odw(n, 0); // 2 to ze na stacku
    vi grp(n);
    std::vector <vi> zbior(n, vi()),klu(n, vi());
    REP(i, m){
        pol[u[i]][c[i]].push_back(v[i]);
        pol[v[i]][c[i]].push_back(u[i]);
    }
    REP(i, n)
        grp[i]=i,zbior[i].emplace_back(i),klu[i].emplace_back(r[i]);
    auto merg=[&](vi &i, vi &j){
        if (i.size()<j.size())
            std::swap(i, j);
        for (int k : j)
            i.emplace_back(k);
        j={};
    };
    auto lac=[&](int i, int j){ // j do i
        for (int k : zbior[j])
            grp[k]=i;
        merg(zbior[i], zbior[j]);
        merg(klu[i], klu[j]);
        for (int k=0; k<cap; ++k)
            merg(pol[i][k], pol[j][k]);
    };
    int wsize=1e9;
    vi wyn;
    std::function <rettype(int)> DFS=[&](int i){
        rettype ret={-1, 0};
        odw[i]=2;
        while (1){
            for (int k : klu[i]){
                while (pol[i][k].size()){
                    int j=grp[pol[i][k].back()];
                    pol[i][k].pop_back();
                    if (j==i)
                        continue;
                    if (odw[j]==1){
                        ret.czybylmin=1;
                        continue;
                    }
                    if (!odw[j]){
                        rettype sr=DFS(j);
                        ret.czybylmin|=sr.czybylmin;
                        if (sr.cof>=0){
                            // iteratory beda rozwalone
                            if (sr.cof==i)
                                goto xd;
                            ret.cof=sr.cof;
                            lac(ret.cof, i);
                            odw[i]=1;
                            return ret;
                        }
                        else
                            ret.czybylmin=1;
                    }
                    else{
                        // trza sie cofnac i zmerge'owac do j
                        ret.cof=j;
                        lac(ret.cof, i);
                        odw[i]=1;
                        return ret;
                    }
                }
            }
            break;
            xd:
            continue;
        }
        if (!ret.czybylmin){
            if (ssize(zbior[i])<wsize)
                wsize=ssize(zbior[i]),wyn.clear();
            if (ssize(zbior[i])==wsize)
                wyn.emplace_back(i);
        }
        odw[i]=1;
        return ret;
    };
    REP(i, n)
        if (!odw[i])
            DFS(i);
    vi ret(r.size(), 0);
    for (auto i : wyn)
        for (auto j : zbior[i])
            ret[j]=1;
    return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 0 / 33