Submission #49522

#	Time	Username	Problem	Language	Result	Execution time	Memory
49522		ho94949	Parachute rings (IOI12_rings)	C++17	100 / 100	2760 ms	120348 KiB

rings

#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 1010101;

struct UF
{
    int ufd[MAXN], N;
    UF(){}
    UF(int n): N(n)
    {
        for(int i=0; i<n; ++i) ufd[i] = i;
    }
    int Find(int a)
    {
        if(a==ufd[a]) return a;
        return ufd[a] = Find(ufd[a]);
    }
    bool Union(int a, int b)
    {
        a = Find(a); b = Find(b);
        if(a==b) return false;
        ufd[a] = b; return true;
    }
};
struct DAT
{
    UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
    DAT(){}
    DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0)
    {
        for(int i=0; i<N; ++i) deg[i] = 0;
    }
    void Add(int a, int b)
    {
        deg[a]++; deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) ovdeg=true;
        if(!uf.Union(a, b))
            if((++numcyc)==1)
                for(int i=0; i<N; ++i)
                    if(uf.Find(i) == uf.Find(a))
                        ++cyclen;
    }
};
DAT global;
int N, M;
pair<int, int> EList[MAXN];
vector<int> conn[MAXN];
int deg[MAXN], ovdeg;
vector<pair<DAT, int> > datas;

void Init(int _N)
{
    N = _N; M = 0; ovdeg = 0;
    DAT d(N); global = d;
}

DAT makeDAT(int x)
{
    DAT d(N);
    for(int i=0; i<M; ++i)
        if(EList[i].first != x && EList[i].second != x)
            d.Add(EList[i].first, EList[i].second);
    return d;
}

void makeGraph()
{
    for(int i=0; i<N; ++i)
    {
        int cnt = (deg[i] >= 3)?1:0;
        for(auto x: conn[i])
            if(deg[x] == 3) ++cnt;
        if(cnt == ovdeg)
            datas.emplace_back(makeDAT(i), i);
    }
}

void Link(int A, int B)
{
    if(ovdeg && datas.size() == 0) return;
    EList[M++] = make_pair(A, B);
    deg[A]++; deg[B]++;
    conn[A].push_back(B);
    conn[B].push_back(A);
    
    int povdeg = ovdeg;
    if(deg[A] == 3) ovdeg++;
    if(deg[B] == 3) ovdeg++;
    if(povdeg == 0 && ovdeg != 0)
        makeGraph();
    else
    {
        if(ovdeg == 0)
            global.Add(A, B);
        else
            for(int i=0; i<datas.size(); ++i)
            {
                if(A!=datas[i].second && B != datas[i].second)
                    datas[i].first.Add(A, B);
                //if(datas[i].first.numcyc != 0 || datas[i].first.ovdeg)
                //    datas.erase(datas.begin()+i);
            }
    }
}

int CountCritical()
{
    if(ovdeg == 0)
    {
        if(global.numcyc == 0) return N;
        if(global.numcyc == 1) return global.cyclen;
        return 0;
    }
    else
    {
        int cnt = 0;
        for(const auto& x: datas)
            if(x.first.numcyc==0 && !x.first.ovdeg) ++cnt;
        return cnt;
    }
}

Compilation message (stderr)

rings.cpp: In constructor 'DAT::DAT(int)':
rings.cpp:29:31: warning: 'DAT::N' will be initialized after [-Wreorder]
     UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
                               ^
rings.cpp:29:8: warning:   'UF DAT::uf' [-Wreorder]
     UF uf; int deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg;
        ^~
rings.cpp:31:5: warning:   when initialized here [-Wreorder]
     DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0)
     ^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:98:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<datas.size(); ++i)
                          ~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31