oj.uz

Submission #102618

# Submission time Handle Problem Language Result Execution time Memory
102618 2019-03-26T09:43:25 Z naoai Parachute rings (IOI12_rings) C++14
52 / 100
 435 ms 88568 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, int type = -1) {
        g[A].push_back(B);
        g[B].push_back(A);

        if (valid == 0)
            return ;

        if (g[A].size() < 3 && g[B].size() < 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[16];

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, 1);

    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() > 4)
            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() > 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:42: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 45 ms 42744 KB Output is correct
2 Correct 65 ms 44536 KB Output is correct
3 Correct 58 ms 44404 KB Output is correct
4 Correct 48 ms 42872 KB Output is correct
5 Correct 50 ms 43256 KB Output is correct
6 Correct 50 ms 43740 KB Output is correct
7 Correct 45 ms 44792 KB Output is correct
8 Correct 48 ms 43512 KB Output is correct
9 Correct 59 ms 45220 KB Output is correct
10 Correct 59 ms 45432 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 88568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42744 KB Output is correct
2 Correct 65 ms 44536 KB Output is correct
3 Correct 58 ms 44404 KB Output is correct
4 Correct 48 ms 42872 KB Output is correct
5 Correct 50 ms 43256 KB Output is correct
6 Correct 50 ms 43740 KB Output is correct
7 Correct 45 ms 44792 KB Output is correct
8 Correct 48 ms 43512 KB Output is correct
9 Correct 59 ms 45220 KB Output is correct
10 Correct 59 ms 45432 KB Output is correct
11 Correct 55 ms 45156 KB Output is correct
12 Correct 91 ms 50424 KB Output is correct
13 Correct 84 ms 48760 KB Output is correct
14 Correct 54 ms 45048 KB Output is correct
15 Correct 59 ms 45944 KB Output is correct
16 Correct 56 ms 44664 KB Output is correct
17 Correct 64 ms 47608 KB Output is correct
18 Correct 70 ms 50936 KB Output is correct
19 Correct 70 ms 44668 KB Output is correct
20 Correct 106 ms 48104 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42744 KB Output is correct
2 Correct 65 ms 44536 KB Output is correct
3 Correct 58 ms 44404 KB Output is correct
4 Correct 48 ms 42872 KB Output is correct
5 Correct 50 ms 43256 KB Output is correct
6 Correct 50 ms 43740 KB Output is correct
7 Correct 45 ms 44792 KB Output is correct
8 Correct 48 ms 43512 KB Output is correct
9 Correct 59 ms 45220 KB Output is correct
10 Correct 59 ms 45432 KB Output is correct
11 Correct 55 ms 45156 KB Output is correct
12 Correct 91 ms 50424 KB Output is correct
13 Correct 84 ms 48760 KB Output is correct
14 Correct 54 ms 45048 KB Output is correct
15 Correct 59 ms 45944 KB Output is correct
16 Correct 56 ms 44664 KB Output is correct
17 Correct 64 ms 47608 KB Output is correct
18 Correct 70 ms 50936 KB Output is correct
19 Correct 70 ms 44668 KB Output is correct
20 Correct 106 ms 48104 KB Output is correct
21 Correct 116 ms 48428 KB Output is correct
22 Correct 165 ms 51664 KB Output is correct
23 Correct 198 ms 54116 KB Output is correct
24 Correct 345 ms 62448 KB Output is correct
25 Correct 78 ms 53752 KB Output is correct
26 Correct 296 ms 65520 KB Output is correct
27 Correct 326 ms 58988 KB Output is correct
28 Correct 304 ms 83308 KB Output is correct
29 Correct 200 ms 78408 KB Output is correct
30 Correct 435 ms 61548 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42744 KB Output is correct
2 Correct 65 ms 44536 KB Output is correct
3 Correct 58 ms 44404 KB Output is correct
4 Correct 48 ms 42872 KB Output is correct
5 Correct 50 ms 43256 KB Output is correct
6 Correct 50 ms 43740 KB Output is correct
7 Correct 45 ms 44792 KB Output is correct
8 Correct 48 ms 43512 KB Output is correct
9 Correct 59 ms 45220 KB Output is correct
10 Correct 59 ms 45432 KB Output is correct
11 Runtime error 99 ms 88568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -