제출 #808809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
808809		pomuchle	열쇠 (IOI21_keys)	C++17	0 / 100	111 ms	211664 KiB

keys

#include <vector>
#define NN 300000
#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 pol[NN][30];
vi find_reachable(vi r, vi u, vi v, vi c) {
    int n=ssize(r),m=ssize(u);
    // r=klucz w wierzch, reszta to kraw
    REP(i, m){
        pol[u[i]][c[i]].push_back(v[i]);
        pol[v[i]][c[i]].push_back(u[i]);
    }
    vi odw(n, 0); // 2 to ze na stacku
    vi grp(n);
    std::vector <vi> zbior(n, vi()),klu(n, vi());
    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]);
        for (int k=0; k<30; ++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])
                for (int j : pol[i][k]){
                    j=grp[j];
                    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=j;
                            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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33