oj.uz

Submission #104289

# Submission time Handle Problem Language Result Execution time Memory
104289 2019-04-04T18:00:10 Z naoai Parachute rings (IOI12_rings) C++14
100 / 100
 2245 ms 124656 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e6 + 5;

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

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

    void init () {
        valid = 1;
        for (int i = 0; i < n; ++ i) {
            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 {
                t[lb] = la;

                if (type == 1)
                    grad[la] += grad[lb];
            }
        } else
            valid = 0;
    }
} root, s3[7];

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

void Init(int N_) {
    n = N_;
    centered = -1;

    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 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(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

rings.cpp: In function 'void invalideaza(int)':
rings.cpp:79: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:135:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g3.size(); ++ i) {
                         ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 30 ms 24312 KB Output is correct
3 Correct 30 ms 24440 KB Output is correct
4 Correct 27 ms 23936 KB Output is correct
5 Correct 31 ms 24064 KB Output is correct
6 Correct 28 ms 24192 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 31 ms 24440 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 51032 KB Output is correct
2 Correct 1479 ms 90408 KB Output is correct
3 Correct 1539 ms 117820 KB Output is correct
4 Correct 1627 ms 75360 KB Output is correct
5 Correct 1636 ms 75604 KB Output is correct
6 Correct 1593 ms 74076 KB Output is correct
7 Correct 1085 ms 124656 KB Output is correct
8 Correct 2159 ms 101440 KB Output is correct
9 Correct 2245 ms 114324 KB Output is correct
10 Correct 1142 ms 73672 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 30 ms 24312 KB Output is correct
3 Correct 30 ms 24440 KB Output is correct
4 Correct 27 ms 23936 KB Output is correct
5 Correct 31 ms 24064 KB Output is correct
6 Correct 28 ms 24192 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 31 ms 24440 KB Output is correct
11 Correct 27 ms 24420 KB Output is correct
12 Correct 36 ms 25088 KB Output is correct
13 Correct 32 ms 24952 KB Output is correct
14 Correct 31 ms 24576 KB Output is correct
15 Correct 29 ms 24924 KB Output is correct
16 Correct 34 ms 24440 KB Output is correct
17 Correct 34 ms 25208 KB Output is correct
18 Correct 30 ms 25856 KB Output is correct
19 Correct 34 ms 24568 KB Output is correct
20 Correct 34 ms 25080 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 30 ms 24312 KB Output is correct
3 Correct 30 ms 24440 KB Output is correct
4 Correct 27 ms 23936 KB Output is correct
5 Correct 31 ms 24064 KB Output is correct
6 Correct 28 ms 24192 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 31 ms 24440 KB Output is correct
11 Correct 27 ms 24420 KB Output is correct
12 Correct 36 ms 25088 KB Output is correct
13 Correct 32 ms 24952 KB Output is correct
14 Correct 31 ms 24576 KB Output is correct
15 Correct 29 ms 24924 KB Output is correct
16 Correct 34 ms 24440 KB Output is correct
17 Correct 34 ms 25208 KB Output is correct
18 Correct 30 ms 25856 KB Output is correct
19 Correct 34 ms 24568 KB Output is correct
20 Correct 34 ms 25080 KB Output is correct
21 Correct 50 ms 26048 KB Output is correct
22 Correct 72 ms 27184 KB Output is correct
23 Correct 108 ms 28016 KB Output is correct
24 Correct 85 ms 29552 KB Output is correct
25 Correct 45 ms 27848 KB Output is correct
26 Correct 92 ms 31188 KB Output is correct
27 Correct 106 ms 28780 KB Output is correct
28 Correct 97 ms 33788 KB Output is correct
29 Correct 85 ms 33104 KB Output is correct
30 Correct 125 ms 29420 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 30 ms 24312 KB Output is correct
3 Correct 30 ms 24440 KB Output is correct
4 Correct 27 ms 23936 KB Output is correct
5 Correct 31 ms 24064 KB Output is correct
6 Correct 28 ms 24192 KB Output is correct
7 Correct 26 ms 24312 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 29 ms 24440 KB Output is correct
10 Correct 31 ms 24440 KB Output is correct
11 Correct 621 ms 51032 KB Output is correct
12 Correct 1479 ms 90408 KB Output is correct
13 Correct 1539 ms 117820 KB Output is correct
14 Correct 1627 ms 75360 KB Output is correct
15 Correct 1636 ms 75604 KB Output is correct
16 Correct 1593 ms 74076 KB Output is correct
17 Correct 1085 ms 124656 KB Output is correct
18 Correct 2159 ms 101440 KB Output is correct
19 Correct 2245 ms 114324 KB Output is correct
20 Correct 1142 ms 73672 KB Output is correct
21 Correct 27 ms 24420 KB Output is correct
22 Correct 36 ms 25088 KB Output is correct
23 Correct 32 ms 24952 KB Output is correct
24 Correct 31 ms 24576 KB Output is correct
25 Correct 29 ms 24924 KB Output is correct
26 Correct 34 ms 24440 KB Output is correct
27 Correct 34 ms 25208 KB Output is correct
28 Correct 30 ms 25856 KB Output is correct
29 Correct 34 ms 24568 KB Output is correct
30 Correct 34 ms 25080 KB Output is correct
31 Correct 50 ms 26048 KB Output is correct
32 Correct 72 ms 27184 KB Output is correct
33 Correct 108 ms 28016 KB Output is correct
34 Correct 85 ms 29552 KB Output is correct
35 Correct 45 ms 27848 KB Output is correct
36 Correct 92 ms 31188 KB Output is correct
37 Correct 106 ms 28780 KB Output is correct
38 Correct 97 ms 33788 KB Output is correct
39 Correct 85 ms 33104 KB Output is correct
40 Correct 125 ms 29420 KB Output is correct
41 Correct 334 ms 40424 KB Output is correct
42 Correct 1008 ms 79864 KB Output is correct
43 Correct 384 ms 58712 KB Output is correct
44 Correct 987 ms 120884 KB Output is correct
45 Correct 1128 ms 94840 KB Output is correct
46 Correct 1245 ms 67104 KB Output is correct
47 Correct 1247 ms 67868 KB Output is correct
48 Correct 668 ms 109924 KB Output is correct
49 Correct 897 ms 67160 KB Output is correct
50 Correct 1012 ms 66648 KB Output is correct
51 Correct 374 ms 63596 KB Output is correct
52 Correct 718 ms 101852 KB Output is correct
53 Correct 620 ms 110540 KB Output is correct
54 Correct 1875 ms 97124 KB Output is correct
55 Correct 1451 ms 96796 KB Output is correct