oj.uz

Submission #49508

# Submission time Handle Problem Language Result Execution time Memory
49508 2018-05-30T06:19:15 Z ho94949 Parachute rings (IOI12_rings) C++17
0 / 100
 1714 ms 92696 KB 
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 1010101;

struct UF
{
    int N;
    int ufd[MAXN];
    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
{
    int N; UF uf; int numcyc; int cyclen;
    DAT(){};
    DAT(int n): N(n), uf(n), numcyc(0), cyclen(0){}
    void Add(int a, int b)
    {
        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();
    switch(state)
    {
        case DEG2: case INF: return;
        case DEG3_1: 
            for(int i=0; i<N; ++i)
                if(deg[i] == 3)
                {
                    specials.push_back(i);
                    for(auto x: conn[i])
                        specials.push_back(x);
                }
            break;
        case DEG3_2:
        case DEG3_3: 
            for(int i=0; i<N; ++i)
                if(deg[i] == 3)
                    specials.push_back(i);
            break;
        case SP1: 
            
            for(int i=0; i<N; ++i)
                if(deg[i] >= 3)
                {
                    int cnt = 1;
                    for(auto x: conn[i])
                        if(deg[x] >= 3) ++cnt;
                    if(cnt == numdeg[3]+numdeg[4])
                        specials.push_back(i);
                }
            break;
    }
    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;
    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);
}
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) ++ans;
        return ans;
    }
}

Compilation message

rings.cpp: In function 'void updatestate(PHASE, int, int)':
rings.cpp:120:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<specials.size(); ++i)
                          ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28024 KB Output is correct
2 Correct 48 ms 48000 KB Output is correct
3 Correct 47 ms 48016 KB Output is correct
4 Correct 30 ms 48016 KB Output is correct
5 Correct 29 ms 48016 KB Output is correct
6 Correct 28 ms 48016 KB Output is correct
7 Correct 49 ms 48020 KB Output is correct
8 Correct 33 ms 48020 KB Output is correct
9 Correct 61 ms 48056 KB Output is correct
10 Incorrect 51 ms 48160 KB Output isn't correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 52656 KB Output is correct
2 Correct 1122 ms 81600 KB Output is correct
3 Correct 397 ms 81600 KB Output is correct
4 Correct 1373 ms 81600 KB Output is correct
5 Correct 1378 ms 81600 KB Output is correct
6 Correct 1335 ms 81600 KB Output is correct
7 Correct 365 ms 81600 KB Output is correct
8 Correct 1489 ms 88240 KB Output is correct
9 Incorrect 1714 ms 92696 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28024 KB Output is correct
2 Correct 48 ms 48000 KB Output is correct
3 Correct 47 ms 48016 KB Output is correct
4 Correct 30 ms 48016 KB Output is correct
5 Correct 29 ms 48016 KB Output is correct
6 Correct 28 ms 48016 KB Output is correct
7 Correct 49 ms 48020 KB Output is correct
8 Correct 33 ms 48020 KB Output is correct
9 Correct 61 ms 48056 KB Output is correct
10 Incorrect 51 ms 48160 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28024 KB Output is correct
2 Correct 48 ms 48000 KB Output is correct
3 Correct 47 ms 48016 KB Output is correct
4 Correct 30 ms 48016 KB Output is correct
5 Correct 29 ms 48016 KB Output is correct
6 Correct 28 ms 48016 KB Output is correct
7 Correct 49 ms 48020 KB Output is correct
8 Correct 33 ms 48020 KB Output is correct
9 Correct 61 ms 48056 KB Output is correct
10 Incorrect 51 ms 48160 KB Output isn't correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28024 KB Output is correct
2 Correct 48 ms 48000 KB Output is correct
3 Correct 47 ms 48016 KB Output is correct
4 Correct 30 ms 48016 KB Output is correct
5 Correct 29 ms 48016 KB Output is correct
6 Correct 28 ms 48016 KB Output is correct
7 Correct 49 ms 48020 KB Output is correct
8 Correct 33 ms 48020 KB Output is correct
9 Correct 61 ms 48056 KB Output is correct
10 Incorrect 51 ms 48160 KB Output isn't correct