oj.uz

Submission #102623

# Submission time Handle Problem Language Result Execution time Memory
102623 2019-03-26T09:54:54 Z naoai Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 211016 KB 
#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];
static int grad[nmax + 1];

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

    void init () {
        valid = 1;
        for (int i = 0; i < n; ++ i) {
            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, 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 && (c1[la] == A && c2[la] == B || c1[la] == B && c2[la] == A))
                    c1[la] = c2[la] = -1;
                else
                    valid = 0;
            } else {
                t[lb] = la;

                if (type == 1)
                    grad[la] += grad[lb];

                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_;
    for (int i = 0; i < n; ++ i)
        grad[i] = 1;

    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] == 1 && root.g[B] == 1 && root.find_tata(A) == root.find_tata(B)) {
        ciclu.push_back(grad[root.find_tata(A)]);
    }

    root.link(A, B, 1);

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

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

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

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

    if (g3.size() == 4) {
        for (auto i : g3) {
            bool ok = 1;
            for (auto j : vec[i]) {
                if (vec[j].size() != 3)
                    ok = 0;
            }

            if (ok == 1)
                cen.push_back(i);
        }
    }

    // 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 3+ 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;
        }
    }
}

Compilation message

rings.cpp: In member function 'void Str::link(int, int, int)':
rings.cpp:47:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if (type == 1 && (c1[la] == A && c2[la] == B || c1[la] == B && c2[la] == A))
                                   ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24064 KB Output is correct
2 Correct 32 ms 25080 KB Output is correct
3 Correct 34 ms 25464 KB Output is correct
4 Correct 25 ms 24064 KB Output is correct
5 Correct 28 ms 24448 KB Output is correct
6 Correct 27 ms 24832 KB Output is correct
7 Correct 24 ms 25340 KB Output is correct
8 Correct 28 ms 24640 KB Output is correct
9 Correct 30 ms 25472 KB Output is correct
10 Correct 37 ms 25508 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2959 ms 126036 KB Output is correct
2 Execution timed out 4099 ms 211016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24064 KB Output is correct
2 Correct 32 ms 25080 KB Output is correct
3 Correct 34 ms 25464 KB Output is correct
4 Correct 25 ms 24064 KB Output is correct
5 Correct 28 ms 24448 KB Output is correct
6 Correct 27 ms 24832 KB Output is correct
7 Correct 24 ms 25340 KB Output is correct
8 Correct 28 ms 24640 KB Output is correct
9 Correct 30 ms 25472 KB Output is correct
10 Correct 37 ms 25508 KB Output is correct
11 Correct 37 ms 25436 KB Output is correct
12 Correct 40 ms 26872 KB Output is correct
13 Incorrect 49 ms 27512 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24064 KB Output is correct
2 Correct 32 ms 25080 KB Output is correct
3 Correct 34 ms 25464 KB Output is correct
4 Correct 25 ms 24064 KB Output is correct
5 Correct 28 ms 24448 KB Output is correct
6 Correct 27 ms 24832 KB Output is correct
7 Correct 24 ms 25340 KB Output is correct
8 Correct 28 ms 24640 KB Output is correct
9 Correct 30 ms 25472 KB Output is correct
10 Correct 37 ms 25508 KB Output is correct
11 Correct 37 ms 25436 KB Output is correct
12 Correct 40 ms 26872 KB Output is correct
13 Incorrect 49 ms 27512 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24064 KB Output is correct
2 Correct 32 ms 25080 KB Output is correct
3 Correct 34 ms 25464 KB Output is correct
4 Correct 25 ms 24064 KB Output is correct
5 Correct 28 ms 24448 KB Output is correct
6 Correct 27 ms 24832 KB Output is correct
7 Correct 24 ms 25340 KB Output is correct
8 Correct 28 ms 24640 KB Output is correct
9 Correct 30 ms 25472 KB Output is correct
10 Correct 37 ms 25508 KB Output is correct
11 Correct 2959 ms 126036 KB Output is correct
12 Execution timed out 4099 ms 211016 KB Time limit exceeded
13 Halted 0 ms 0 KB -