oj.uz

Submission #167523

# Submission time Handle Problem Language Result Execution time Memory
167523 2019-12-08T19:01:17 Z faremy Parachute rings (IOI12_rings) C++14
100 / 100
 1526 ms 94676 KB 
/*
Not my code. Source: https://github.com/BarishNamazov/IOI/blob/master/ioi2012_rings.cpp
I don't wanna spend 3 more hours coding a solution that won't get f*cked by constant factor.
*/


#include <bits/stdc++.h>

using namespace std;

const int MX = 1000006;

int N;
int par[MX], par4[4][MX];
int Find(int x) {
    return par[x] < 0 ? x : (par[x] = Find(par[x]));
}
void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (-par[x] < -par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
}
int Find4(int x, int i) {
    return par4[i][x] < 0 ? x : (par4[i][x] = Find4(par4[i][x], i));
}
void Union4(int x, int y, int i) {
    x = Find4(x, i), y = Find4(y, i);
    if (x == y) return;
    if (-par4[i][x] < -par4[i][y]) swap(x, y);
    par4[i][x] += par4[i][y];
    par4[i][y] = x;
}

void Init(int N_) {
    N = N_;
    for (int i = 0; i < N; i++) {
        par[i] = -1;
        par4[0][i] = par4[1][i] = par4[2][i] = par4[3][i] = -1;
    }
}

vector <int> g[MX];
int has4 = 0, cycle = 0, cycle_size = 0;
int can[4], deg4[4][MX], ok[4], deg[MX];
void add(int a, int b) {
    for (int i = 0; i < 4; i++) {
        if (can[i] == a || can[i] == b || ok[i] == 0) {
            continue;
        }
        deg4[i][a]++, deg4[i][b]++;
        if (deg4[i][a] == 3 || deg4[i][b] == 3) {
            ok[i] = 0;
            continue;
        }
        if (deg4[i][a] == 2 && deg4[i][b] == 2 && Find4(a, i) == Find4(b, i)) {
            ok[i] = 0;
            continue;
        }
        Union4(a, b, i);
    }
}

void wehave4(int v) {
    has4 = 1;
    can[0] = v;
    for (int i = 0; i < 3; i++) {
        can[i + 1] = g[v][i];
    }
    for (int i = 0; i < 4; i++) {
        ok[i] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j : g[i]) {
            if (i < j) {
                add(i, j);
            }
        }
    }
}

void Link(int A, int B) {
    if (has4 == 0) {
        deg[A]++, deg[B]++;
        g[A].push_back(B);
        g[B].push_back(A);
        if (deg[A] == 3) {
            wehave4(A);
            return;
        }
        if (deg[B] == 3) {
            wehave4(B);
            return;
        }
        if (deg[A] == 2 && deg[B] == 2 && Find(A) == Find(B)) {
            cycle++;
            cycle_size = -par[Find(A)];
        }
        Union(A, B);
    } else {
        add(A, B);
    }
}

int CountCritical() {
    if (has4 == 0) {
        if (cycle == 1) return cycle_size;
        else if (cycle > 1) return 0;
        else return N;
    }
    return ok[0] + ok[1] + ok[2] + ok[3];
}

Subtask #1
20.0 / 20.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 54508 KB Output is correct
2 Correct 628 ms 70648 KB Output is correct
3 Correct 349 ms 64836 KB Output is correct
4 Correct 1135 ms 80124 KB Output is correct
5 Correct 1161 ms 80216 KB Output is correct
6 Correct 1113 ms 78928 KB Output is correct
7 Correct 341 ms 64888 KB Output is correct
8 Correct 1314 ms 88312 KB Output is correct
9 Correct 1526 ms 94676 KB Output is correct
10 Correct 859 ms 77048 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 26 ms 24184 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 26 ms 24184 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 25 ms 24184 KB Output is correct
9 Correct 26 ms 24312 KB Output is correct
10 Correct 26 ms 24312 KB Output is correct
11 Correct 28 ms 24184 KB Output is correct
12 Correct 32 ms 24696 KB Output is correct
13 Correct 29 ms 24568 KB Output is correct
14 Correct 27 ms 24312 KB Output is correct
15 Correct 27 ms 24568 KB Output is correct
16 Correct 28 ms 24572 KB Output is correct
17 Correct 27 ms 24440 KB Output is correct
18 Correct 28 ms 24824 KB Output is correct
19 Correct 29 ms 24572 KB Output is correct
20 Correct 29 ms 24696 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 26 ms 24184 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 26 ms 24184 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 25 ms 24184 KB Output is correct
9 Correct 26 ms 24312 KB Output is correct
10 Correct 26 ms 24312 KB Output is correct
11 Correct 28 ms 24184 KB Output is correct
12 Correct 32 ms 24696 KB Output is correct
13 Correct 29 ms 24568 KB Output is correct
14 Correct 27 ms 24312 KB Output is correct
15 Correct 27 ms 24568 KB Output is correct
16 Correct 28 ms 24572 KB Output is correct
17 Correct 27 ms 24440 KB Output is correct
18 Correct 28 ms 24824 KB Output is correct
19 Correct 29 ms 24572 KB Output is correct
20 Correct 29 ms 24696 KB Output is correct
21 Correct 47 ms 26488 KB Output is correct
22 Correct 57 ms 27996 KB Output is correct
23 Correct 66 ms 29048 KB Output is correct
24 Correct 55 ms 27128 KB Output is correct
25 Correct 39 ms 27016 KB Output is correct
26 Correct 58 ms 28664 KB Output is correct
27 Correct 76 ms 29576 KB Output is correct
28 Correct 55 ms 28536 KB Output is correct
29 Correct 54 ms 28792 KB Output is correct
30 Correct 95 ms 30456 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 26 ms 24184 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 26 ms 24184 KB Output is correct
7 Correct 23 ms 24056 KB Output is correct
8 Correct 25 ms 24184 KB Output is correct
9 Correct 26 ms 24312 KB Output is correct
10 Correct 26 ms 24312 KB Output is correct
11 Correct 426 ms 54508 KB Output is correct
12 Correct 628 ms 70648 KB Output is correct
13 Correct 349 ms 64836 KB Output is correct
14 Correct 1135 ms 80124 KB Output is correct
15 Correct 1161 ms 80216 KB Output is correct
16 Correct 1113 ms 78928 KB Output is correct
17 Correct 341 ms 64888 KB Output is correct
18 Correct 1314 ms 88312 KB Output is correct
19 Correct 1526 ms 94676 KB Output is correct
20 Correct 859 ms 77048 KB Output is correct
21 Correct 28 ms 24184 KB Output is correct
22 Correct 32 ms 24696 KB Output is correct
23 Correct 29 ms 24568 KB Output is correct
24 Correct 27 ms 24312 KB Output is correct
25 Correct 27 ms 24568 KB Output is correct
26 Correct 28 ms 24572 KB Output is correct
27 Correct 27 ms 24440 KB Output is correct
28 Correct 28 ms 24824 KB Output is correct
29 Correct 29 ms 24572 KB Output is correct
30 Correct 29 ms 24696 KB Output is correct
31 Correct 47 ms 26488 KB Output is correct
32 Correct 57 ms 27996 KB Output is correct
33 Correct 66 ms 29048 KB Output is correct
34 Correct 55 ms 27128 KB Output is correct
35 Correct 39 ms 27016 KB Output is correct
36 Correct 58 ms 28664 KB Output is correct
37 Correct 76 ms 29576 KB Output is correct
38 Correct 55 ms 28536 KB Output is correct
39 Correct 54 ms 28792 KB Output is correct
40 Correct 95 ms 30456 KB Output is correct
41 Correct 262 ms 47864 KB Output is correct
42 Correct 672 ms 76328 KB Output is correct
43 Correct 248 ms 52440 KB Output is correct
44 Correct 339 ms 72360 KB Output is correct
45 Correct 422 ms 73940 KB Output is correct
46 Correct 786 ms 81456 KB Output is correct
47 Correct 933 ms 82348 KB Output is correct
48 Correct 313 ms 71544 KB Output is correct
49 Correct 738 ms 83412 KB Output is correct
50 Correct 766 ms 82776 KB Output is correct
51 Correct 243 ms 58360 KB Output is correct
52 Correct 318 ms 63664 KB Output is correct
53 Correct 280 ms 70532 KB Output is correct
54 Correct 870 ms 86236 KB Output is correct
55 Correct 435 ms 71088 KB Output is correct