oj.uz

Submission #102666

# Submission time Handle Problem Language Result Execution time Memory
102666 2019-03-26T14:53:14 Z naoai Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 224092 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];

struct Str {
    bool valid;
    int c1[nmax + 1], c2[nmax + 1];
    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] = 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 {
                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[7];

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 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) {
    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(root.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() > 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);
    }

    // dc nu exista cen, at tin pentru cele 3 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 (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() > 4) // 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;
        }
    }
}

Compilation message

rings.cpp: In member function 'void Str::link(int, int, int)':
rings.cpp:46:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if (type == 1 && (c1[la] == A && c2[la] == B || c1[la] == B && c2[la] == A))
                                   ~~~~~~~~~~~~^~~~~~~~~~~~~~
rings.cpp: In function 'void invalideaza(int)':
rings.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < trk.size(); ++ i) {
                     ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 31 ms 25216 KB Output is correct
3 Correct 39 ms 25464 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 30 ms 24548 KB Output is correct
6 Correct 39 ms 24824 KB Output is correct
7 Correct 29 ms 25080 KB Output is correct
8 Correct 30 ms 24668 KB Output is correct
9 Correct 31 ms 25332 KB Output is correct
10 Correct 33 ms 25528 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2950 ms 119948 KB Output is correct
2 Execution timed out 4018 ms 224092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 31 ms 25216 KB Output is correct
3 Correct 39 ms 25464 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 30 ms 24548 KB Output is correct
6 Correct 39 ms 24824 KB Output is correct
7 Correct 29 ms 25080 KB Output is correct
8 Correct 30 ms 24668 KB Output is correct
9 Correct 31 ms 25332 KB Output is correct
10 Correct 33 ms 25528 KB Output is correct
11 Correct 33 ms 25468 KB Output is correct
12 Correct 40 ms 27264 KB Output is correct
13 Correct 46 ms 27000 KB Output is correct
14 Correct 33 ms 26368 KB Output is correct
15 Correct 38 ms 27260 KB Output is correct
16 Correct 42 ms 25848 KB Output is correct
17 Correct 44 ms 27512 KB Output is correct
18 Correct 48 ms 29176 KB Output is correct
19 Correct 39 ms 25848 KB Output is correct
20 Correct 39 ms 27008 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 31 ms 25216 KB Output is correct
3 Correct 39 ms 25464 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 30 ms 24548 KB Output is correct
6 Correct 39 ms 24824 KB Output is correct
7 Correct 29 ms 25080 KB Output is correct
8 Correct 30 ms 24668 KB Output is correct
9 Correct 31 ms 25332 KB Output is correct
10 Correct 33 ms 25528 KB Output is correct
11 Correct 33 ms 25468 KB Output is correct
12 Correct 40 ms 27264 KB Output is correct
13 Correct 46 ms 27000 KB Output is correct
14 Correct 33 ms 26368 KB Output is correct
15 Correct 38 ms 27260 KB Output is correct
16 Correct 42 ms 25848 KB Output is correct
17 Correct 44 ms 27512 KB Output is correct
18 Correct 48 ms 29176 KB Output is correct
19 Correct 39 ms 25848 KB Output is correct
20 Correct 39 ms 27008 KB Output is correct
21 Correct 87 ms 29556 KB Output is correct
22 Correct 153 ms 32840 KB Output is correct
23 Correct 211 ms 35156 KB Output is correct
24 Correct 263 ms 42608 KB Output is correct
25 Correct 62 ms 35960 KB Output is correct
26 Correct 246 ms 46192 KB Output is correct
27 Correct 296 ms 39684 KB Output is correct
28 Correct 263 ms 52696 KB Output is correct
29 Correct 157 ms 45684 KB Output is correct
30 Correct 437 ms 42268 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 31 ms 25216 KB Output is correct
3 Correct 39 ms 25464 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 30 ms 24548 KB Output is correct
6 Correct 39 ms 24824 KB Output is correct
7 Correct 29 ms 25080 KB Output is correct
8 Correct 30 ms 24668 KB Output is correct
9 Correct 31 ms 25332 KB Output is correct
10 Correct 33 ms 25528 KB Output is correct
11 Correct 2950 ms 119948 KB Output is correct
12 Execution timed out 4018 ms 224092 KB Time limit exceeded
13 Halted 0 ms 0 KB -