Submission #104287

#	Time	Username	Problem	Language	Result	Execution time	Memory
104287		naoai	Parachute rings (IOI12_rings)	C++14	100 / 100	3365 ms	157896 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e6 + 5;

static int n;
static vector<int> ciclu;
static vector<int> cen, g3, trk;
static vector<int> vec[nmax + 1];

struct Str {
    bool valid;
    int grad[nmax + 1], t[nmax + 1];
    int g[nmax + 1];

    void init () {
        valid = 1;
        for (int i = 0; i < n; ++ i) {
            grad[i] = 1;
            t[i] = i;
        }
    }

    inline int find_tata (int x) {
        if (x == t[x]) return x;
        return t[x] = find_tata(t[x]);
    }

    void link (int A, int B, int type = -1) {
        ++ g[A]; ++ g[B];
        if (type == 1) {
            vec[A].push_back(B);
            vec[B].push_back(A);
        }

        if (valid == 0)
            return ;

        if (g[A] < 3 && g[B] < 3) {
            int la = find_tata(A);
            int lb = find_tata(B);

            if (la == lb) { // apare ciclu
                if (!(type == 1 && (g[A] == 2 && g[B] == 2)))
                    valid = 0;
            } else {
                if (grad[la] < grad[lb]) {
                    swap(la, lb);
                    swap(A, B);
                }

                grad[la] += grad[lb];
                t[lb] = la;
            }
        } else
            valid = 0;
    }
} root, s3[7];

vector<pair<int, int>> e;
int centered;

void Init(int N_) {
    n = N_;
    centered = -1;
    root.init();
}

bool nuexista (int i) {
    bool ok = 1;
    for (auto j : trk)
        if (i == j) ok = 0;
    return ok;
}

void invalideaza (int x) {
    for (int i = 0; i < trk.size(); ++ i) {
        if (trk[i] == x) continue;

        bool ok = 0;
        for (auto j : vec[x])
            if (trk[i] == j)
                ok = 1;

        if (ok == 0) {
            s3[i].valid = 0;
        }
    }
}

void Link(int A, int B) {
    if (root.g[A] == 1 && root.g[B] == 1 && root.find_tata(A) == root.find_tata(B)) {
        ciclu.push_back(root.grad[root.find_tata(A)]);
    }

    e.push_back({A, B});
    root.link(A, B, 1);

    int old3 = trk.size();

    if (cen.size() == 0 && (root.g[A] >= 3 || root.g[B] >= 3)) {
        if (g3.size() > 4)
            return ;

        if (root.g[A] == 3) {
            g3.push_back(A);
            if (nuexista(A))
                trk.push_back(A);
            for (auto i : vec[A]) {
                if (g3.size() == 1)
                    trk.push_back(i);
            }

            invalideaza(A);
        }
        if (root.g[B] == 3) {
            g3.push_back(B);
            if (nuexista(B))
                trk.push_back(B);
            for (auto i : vec[B]) {
                if (g3.size() == 1)
                    trk.push_back(i);
            }

            invalideaza(B);
        }

        if (root.g[A] > 3) cen.push_back(A);
        if (root.g[B] > 3) cen.push_back(B);
    }

    if (centered == -1 && cen.size() == 1 && g3.size() <= 4) {
        for (int i = 0; i < g3.size(); ++ i) {
            if (g3[i] == cen[0])
                centered = i;
        }
    }

    // dc nu exista cen, at tin pentru cele 4 g3 uri cum arata fara fiecare
    if (cen.size() == 0) {
        if (g3.size() > 4)
            return ;

        for (int i = old3; i < (int)trk.size(); ++ i) {
            s3[i].init();

            for (auto j : e)
                if (j.first != trk[i] && j.second != trk[i])
                    s3[i].link(j.first, j.second);
        }

        for (int i = 0; i < old3; ++ i)
            if (A != trk[i] && B != trk[i])
                s3[i].link(A, B);
    }

    if (cen.size() == 1)
        if (A != cen[0] && B != cen[0])
            s3[centered].link(A, B);
}

int CountCritical() {
    if (ciclu.size() > 1 || cen.size() > 1) {
        return 0;
    }

    if (g3.size() == 0) {
        if (ciclu.size() == 0)
            return n;
        return ciclu[0];
    } else {
        if (cen.size() == 0 && g3.size() > 4) // daca sunt 4+ trebuie sa aiba un centru
            return 0;

        if (cen.size()) {
            return s3[centered].valid;
        } else {
            int cnt = 0;
            for (int i = 0; i < (int)trk.size(); ++ i) {
                cnt += s3[i].valid;
            }
            return cnt;
        }
    }
}

Compilation message (stderr)

rings.cpp: In function 'void invalideaza(int)':
rings.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < trk.size(); ++ i) {
                     ~~^~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:134:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g3.size(); ++ i) {
                         ~~^~~~~~~~~~~

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