oj.uz

답안 #102538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102538 2019-03-25T19:12:16 Z naoai 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 77 ms 69816 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 5;

static int n;
static vector<int> ciclu;
static vector<int> cen, g3, trk;

struct Str {
    bool valid;
    int c1[nmax + 1], c2[nmax + 1];
    int grad[nmax + 1], t[nmax + 1];
    vector<int> g[nmax + 1];

    void init () {
        valid = 1;
        for (int i = 0; i < n; ++ i) {
            grad[i] = 1;
            t[i] = c1[i] = c2[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) {
        if (valid == 0)
            return ;

        g[A].push_back(B);
        g[B].push_back(A);

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

            if (la == lb) { // apare ciclu
                valid = 0;
            } else {
                if (grad[la] < grad[lb]) {
                    swap(la, lb);
                    swap(A, B);
                }

                grad[la] += grad[lb];
                t[lb] = la;

                if (A == c1[la]) {
                    c1[la] = c1[lb] + c2[lb] - B;
                } else {
                    c2[la] = c1[lb] + c2[lb] - B;
                }
            }
        } else
            valid = 0;
    }
} root, centered, s3[12];

static vector<pair<int, int>> e;
static map<pair<int, int>, bool> mp;

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

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

void Link(int A, int B) {
    e.push_back({A, B});
    mp[{A, B}] = mp[{B, A}] = 1;

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

    root.link(A, B);

    int oldcen = cen.size();
    int old3 = trk.size();

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

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

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

    // dc nu exista cen, at tin pentru cele 3 g3 uri cum arata fara fiecare
    if (cen.size() == 0) {
        if (g3.size() > 3)
            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 (oldcen == 0 && cen.size() == 1) { // a aparut bossu refac tot
        centered.init();

        for (auto i : e)
            if (i.first != cen[0] && i.second != cen[0])
                centered.link(i.first, i.second);
    }

    if (cen.size() == 1 && oldcen == 1)
        if (A != cen[0] && B != cen[0])
            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() > 3) // daca sunt 4+ trebuie sa aiba un centru
            return 0;

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

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 33400 KB Output is correct
2 Correct 43 ms 34808 KB Output is correct
3 Incorrect 48 ms 34732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 69816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 33400 KB Output is correct
2 Correct 43 ms 34808 KB Output is correct
3 Incorrect 48 ms 34732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 33400 KB Output is correct
2 Correct 43 ms 34808 KB Output is correct
3 Incorrect 48 ms 34732 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 33400 KB Output is correct
2 Correct 43 ms 34808 KB Output is correct
3 Incorrect 48 ms 34732 KB Output isn't correct
4 Halted 0 ms 0 KB -