Submission #49517

#	Time	Username	Problem	Language	Result	Execution time	Memory
49517		ho94949	Parachute rings (IOI12_rings)	C++17	100 / 100	1857 ms	99708 KiB

rings

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

const int MAXN = 1010101;

struct UF
{
    int ufd[MAXN];
    int 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; char 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 = 1;
        
        if(!uf.Union(a, b)) 
            if((++numcyc) == 1)
                for(int i=0; i<N; ++i)
                    if(uf.Find(i) == uf.Find(a))
                        ++cyclen;
    }
};
enum PHASE {DEG2, DEG3_1, DEG3_2, DEG3_3, SP1, INF};
PHASE state;

DAT global;


int N, M;
pair<int, int> EList[MAXN];
vector<int> conn[MAXN];
int deg[MAXN], numdeg[5];

vector<int> specials;
vector<DAT> datas;

void Init(int _N) {
    N = _N; M = 0; numdeg[0] = N;
    DAT d(N); global = d;
    state = DEG2;
}
void updatespecials()
{
    for(auto x: specials)
    {
        DAT d(N);
        for(int i=0; i<M; ++i)
        {
            if(EList[i].first == x || EList[i].second == x) continue;
            d.Add(EList[i].first, EList[i].second);
        }
        datas.push_back(d);
    }
}
void makestate(PHASE state)
{
    specials.clear(); datas.clear();
    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 == numdeg[3] + numdeg[4])
            specials.push_back(i);
    }
    updatespecials();
}

void updatestate(PHASE state, int A, int B)
{
    switch(state)
    {
        case DEG2:
            global.Add(A, B);
            break;
        default:
            for(int i=0; i<specials.size(); ++i)
            {
                if(specials[i] == A || specials[i] == B) continue;
                datas[i].Add(A, B);
            }
            break;
    }
}

void Link(int A, int B) {
    if(state == INF) return;
    if(state != DEG2 && datas.size() == 0){state = INF; return;}
    EList[M++] = make_pair(A, B);
    numdeg[min(4, deg[A])]--; numdeg[min(4, deg[B])]--;
    deg[A]++; deg[B]++;
    numdeg[min(4, deg[A])]++; numdeg[min(4, deg[B])]++;
    conn[A].push_back(B);
    conn[B].push_back(A);
    
    
    PHASE newstate = DEG2;
    if(numdeg[4] >= 2){ state = INF; return;}
    else if(numdeg[4] == 1 || numdeg[3] >= 4) newstate = SP1;
    else if(numdeg[3] == 3) newstate = DEG3_3;
    else if(numdeg[3] == 2) newstate = DEG3_2;
    else if(numdeg[3] == 1) newstate = DEG3_1;
    else newstate = DEG2;
    if(state != newstate)
    {
        state = newstate;
        makestate(state);
    }
    else updatestate(state, A, B);
}
//#include<cstdio>
int CountCritical() {
    //if(state == DEG2) puts("DEG2");
    //printf(">%d %d\n", state, (int)datas.size());
    int ans = 0;
    switch(state)
    {
    case DEG2:
        switch(global.numcyc)
        {
            case 0: return N;
            case 1: return global.cyclen;
            default: return 0;
        }
    case INF:
        return 0;
    default:
        for(const auto& x: datas)
            if(x.numcyc==0 && !x.ovdeg ) ++ans;
        return ans;
    }
}

Compilation message (stderr)

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

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