oj.uz

Submission #157335

# Submission time Handle Problem Language Result Execution time Memory
157335 2019-10-10T20:10:52 Z dolphingarlic Parachute rings (IOI12_rings) C++14
100 / 100
 1803 ms 98800 KB 
#include <cassert>
#include <cstdio>
#include <vector>

using namespace std;

int const MAXN = 1000000;

int n;
bool quadruplication = 0;

int numcycles = 0;
int cycle_length;  // If numcycles==1, here we store the length of the only
                   // cycle

int other_endpoint[4][MAXN];  // -1 if the node is not an endpoint, otherwise
                              // the other endpoint
vector<int> neighbours[MAXN];

int destroyed[4];  // The destroyed node of each graph (only if
                   // quadruplication==TRUE)
int degree[4][MAXN];
bool islinear[4];  // Whether each graph is linear or not

void Init(int k) {
    n = k;

    for (int i = 0; i < n; ++i) {
        other_endpoint[0][i] = i;
    }
}

void add_new_edge(int x, int y) {
    // Adds an edge in case of quadruplication

    for (int i = 0; i < 4; ++i) {
        // Operating on graph i

        if (!islinear[i]) continue;
        if (x == destroyed[i] || y == destroyed[i]) continue;

        degree[i][x]++;
        degree[i][y]++;

        assert(degree[i][x] <= 3 && degree[i][y] <= 3);

        if (degree[i][x] == 3 || degree[i][y] == 3) {
            islinear[i] = 0;
            continue;
        }

        if (other_endpoint[i][x] == y) {
            // Cycle!

            islinear[i] = 0;
            continue;
        }

        int a = other_endpoint[i][x];
        int b = other_endpoint[i][y];

        other_endpoint[i][x] = -1;
        other_endpoint[i][y] = -1;
        other_endpoint[i][a] = b;
        other_endpoint[i][b] = a;
    }
}

void quadruplicate(int x) {
    quadruplication = 1;

    destroyed[0] = x;
    destroyed[1] = neighbours[x][0];
    destroyed[2] = neighbours[x][1];
    destroyed[3] = neighbours[x][2];

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < n; ++j) {
            other_endpoint[i][j] = j;
            degree[i][j] = 0;
        }
    }

    for (int i = 0; i < 4; ++i) {
        islinear[i] = 1;
    }

    for (int k = 0; k < n; ++k) {
        for (vector<int>::iterator j = neighbours[k].begin();
             j != neighbours[k].end(); ++j) {
            if (k < (*j)) add_new_edge(k, (*j));
        }
    }
}

void Link(int xx, int yy) {
    int x = xx;
    int y = yy;

    if (quadruplication == 0) {
        neighbours[x].push_back(y);
        neighbours[y].push_back(x);

        degree[0][x]++;
        degree[0][y]++;

        // If a node has degree 3, only it or its neighbours can be critical. So
        // we can keep track of each of the 4 graphs obtained by removing one of
        // these 4 nodes.
        if (degree[0][x] == 3) {
            quadruplicate(x);
            return;
        }
        if (degree[0][y] == 3) {
            quadruplicate(y);
            return;
        }

        // If their degree is < 3, then they were necessarily endpoints!

        if (other_endpoint[0][x] != y) {  // A longer path is formed
            int a = other_endpoint[0][x];
            int b = other_endpoint[0][y];

            other_endpoint[0][x] = -1;
            other_endpoint[0][y] = -1;
            other_endpoint[0][a] = b;
            other_endpoint[0][b] = a;
        } else {  // A cycle is formed
            numcycles++;
            if (numcycles == 1) {
                int length = 1;
                int previous_node = x;
                int current_node = neighbours[x][0];

                while (current_node != x) {
                    int possibility = neighbours[current_node][0];
                    if (possibility == previous_node)
                        possibility = neighbours[current_node][1];

                    previous_node = current_node;
                    current_node = possibility;

                    length++;
                }

                cycle_length = length;
            }
        }
    }

    else {
        add_new_edge(x, y);
    }
}

int CountCritical() {
    if (quadruplication == 0) {
        switch (numcycles) {
            case 0:
                return n;

            case 1:
                return cycle_length;

            default:
                return 0;
        }

    } else {
        int answer = 0;
        for (int i = 0; i < 4; ++i) {
            if (islinear[i]) answer++;
        }
        return answer;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 27 ms 24036 KB Output is correct
6 Correct 26 ms 24132 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 26 ms 24056 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24144 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 51264 KB Output is correct
2 Correct 793 ms 73544 KB Output is correct
3 Correct 344 ms 68216 KB Output is correct
4 Correct 1206 ms 76548 KB Output is correct
5 Correct 1185 ms 76404 KB Output is correct
6 Correct 1417 ms 74940 KB Output is correct
7 Correct 336 ms 67836 KB Output is correct
8 Correct 1509 ms 92024 KB Output is correct
9 Correct 1803 ms 98800 KB Output is correct
10 Correct 807 ms 73880 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 27 ms 24036 KB Output is correct
6 Correct 26 ms 24132 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 26 ms 24056 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24144 KB Output is correct
11 Correct 25 ms 24184 KB Output is correct
12 Correct 36 ms 24568 KB Output is correct
13 Correct 34 ms 24440 KB Output is correct
14 Correct 26 ms 24312 KB Output is correct
15 Correct 27 ms 24568 KB Output is correct
16 Correct 31 ms 24440 KB Output is correct
17 Correct 33 ms 24324 KB Output is correct
18 Correct 28 ms 24716 KB Output is correct
19 Correct 29 ms 24312 KB Output is correct
20 Correct 28 ms 24568 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 27 ms 24036 KB Output is correct
6 Correct 26 ms 24132 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 26 ms 24056 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24144 KB Output is correct
11 Correct 25 ms 24184 KB Output is correct
12 Correct 36 ms 24568 KB Output is correct
13 Correct 34 ms 24440 KB Output is correct
14 Correct 26 ms 24312 KB Output is correct
15 Correct 27 ms 24568 KB Output is correct
16 Correct 31 ms 24440 KB Output is correct
17 Correct 33 ms 24324 KB Output is correct
18 Correct 28 ms 24716 KB Output is correct
19 Correct 29 ms 24312 KB Output is correct
20 Correct 28 ms 24568 KB Output is correct
21 Correct 51 ms 25632 KB Output is correct
22 Correct 59 ms 26616 KB Output is correct
23 Correct 73 ms 27524 KB Output is correct
24 Correct 54 ms 27840 KB Output is correct
25 Correct 38 ms 27384 KB Output is correct
26 Correct 54 ms 27896 KB Output is correct
27 Correct 76 ms 28280 KB Output is correct
28 Correct 53 ms 27768 KB Output is correct
29 Correct 51 ms 27896 KB Output is correct
30 Correct 85 ms 28920 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 27 ms 24036 KB Output is correct
6 Correct 26 ms 24132 KB Output is correct
7 Correct 24 ms 24056 KB Output is correct
8 Correct 26 ms 24056 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 26 ms 24144 KB Output is correct
11 Correct 462 ms 51264 KB Output is correct
12 Correct 793 ms 73544 KB Output is correct
13 Correct 344 ms 68216 KB Output is correct
14 Correct 1206 ms 76548 KB Output is correct
15 Correct 1185 ms 76404 KB Output is correct
16 Correct 1417 ms 74940 KB Output is correct
17 Correct 336 ms 67836 KB Output is correct
18 Correct 1509 ms 92024 KB Output is correct
19 Correct 1803 ms 98800 KB Output is correct
20 Correct 807 ms 73880 KB Output is correct
21 Correct 25 ms 24184 KB Output is correct
22 Correct 36 ms 24568 KB Output is correct
23 Correct 34 ms 24440 KB Output is correct
24 Correct 26 ms 24312 KB Output is correct
25 Correct 27 ms 24568 KB Output is correct
26 Correct 31 ms 24440 KB Output is correct
27 Correct 33 ms 24324 KB Output is correct
28 Correct 28 ms 24716 KB Output is correct
29 Correct 29 ms 24312 KB Output is correct
30 Correct 28 ms 24568 KB Output is correct
31 Correct 51 ms 25632 KB Output is correct
32 Correct 59 ms 26616 KB Output is correct
33 Correct 73 ms 27524 KB Output is correct
34 Correct 54 ms 27840 KB Output is correct
35 Correct 38 ms 27384 KB Output is correct
36 Correct 54 ms 27896 KB Output is correct
37 Correct 76 ms 28280 KB Output is correct
38 Correct 53 ms 27768 KB Output is correct
39 Correct 51 ms 27896 KB Output is correct
40 Correct 85 ms 28920 KB Output is correct
41 Correct 249 ms 39944 KB Output is correct
42 Correct 732 ms 69588 KB Output is correct
43 Correct 254 ms 57924 KB Output is correct
44 Correct 330 ms 65144 KB Output is correct
45 Correct 479 ms 65996 KB Output is correct
46 Correct 750 ms 68444 KB Output is correct
47 Correct 1092 ms 69268 KB Output is correct
48 Correct 314 ms 63788 KB Output is correct
49 Correct 778 ms 67776 KB Output is correct
50 Correct 816 ms 67292 KB Output is correct
51 Correct 244 ms 53788 KB Output is correct
52 Correct 313 ms 57872 KB Output is correct
53 Correct 276 ms 62584 KB Output is correct
54 Correct 1123 ms 79804 KB Output is correct
55 Correct 479 ms 64052 KB Output is correct