oj.uz

Submission #433066

# Submission time Handle Problem Language Result Execution time Memory
433066 2021-06-18T19:34:10 Z someone Parachute rings (IOI12_rings) C++14
37 / 100
 2490 ms 154888 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 42;

struct UF {
    bool isChain = true, tree[N];
    int par[N], deg[N], diff[N], sz[N], nbCycle = 0, total = 0;

    void init(int n) {
        for(int i = 0; i < n; i++) {
            sz[i] = 1;
            par[i] = i;
            deg[i] = 0;
            diff[i] = -1;
            tree[i] = true;
        }
    }

    int F(int i) {
        if(par[i] == i)
            return i;
        return par[i] = F(par[i]);
    }

    int U(int a, int b) {
        deg[a]++;
        deg[b]++;
        int d = max(deg[a], deg[b]);
        if(d > 2)
            isChain = false;
        a = F(a), b = F(b);
        if(a == b) {
            if(tree[a]) {
                total += sz[a];
                nbCycle++;
            }
            diff[a]++;
            isChain = false;
            tree[a] = false;
            return d;
        }
        if(sz[b] < sz[a])
            swap(a, b);
        par[a] = b;
        sz[b] += sz[a];
        diff[b] += diff[a] + 1;
        if(diff[b] != -1)
            isChain = false;
        return d;
    }
};

UF uf[6];
vector<int> adj[N];
int n, maxi = 0, nbCrit, no[6];

void create(int i, int iNot) {
    no[i] = iNot;
    for(int j = 0; j <= n; j++)
        if(j != no[i])
            for(int k : adj[j])
                if(k != no[i] && j < k)
                    uf[i].U(j, k);
}

void Init(int N_) {
    n = N_;
    nbCrit = N_;
    for(int i = 0; i < 6; i++)
        uf[i].init(N_);
}

void Link(int A, int B) {
    adj[A].push_back(B);
    adj[B].push_back(A);
    int newMax = uf[0].U(A, B);
    if(maxi >= 4) {
        uf[5].U(A, B);
        if(uf[5].isChain)
            nbCrit = 1;
    } else if(maxi == 3) {
        if(newMax == 4) {
            maxi = newMax;
            int imax = 0;
            for(int i = 1; i < n; i++)
                if(adj[imax].size() < adj[i].size())
                    imax = i;
            create(5, imax);
            if(uf[5].isChain)
                nbCrit = 1;
            else
                nbCrit = 0;
        } else {
            nbCrit = 0;
            for(int i = 1; i < 5; i++) {
                if(A != no[i] && B != no[i])
                    uf[i].U(A, B);
                if(uf[i].isChain)
                    nbCrit++;
            }
        }
    } else {
        if(newMax == 3) {
            maxi = newMax;
            int imax = 0;
            for(int i = 1; i < n; i++)
                if(adj[imax].size() < adj[i].size())
                    imax = i;
            create(1, imax);
            for(int j = 0; j < 3; j++)
                create(j + 2, adj[imax][j]);
            nbCrit = 0;
            for(int i = 1; i < 5; i++)
                if(uf[i].isChain)
                    nbCrit++;
        } else {
            if(uf[0].nbCycle == 0) {
                nbCrit = n;
            } else if(uf[0].nbCycle == 1) {
                nbCrit = uf[0].total;
            } else {
                nbCrit = 0;
            }
        }
    }
}

int CountCritical() {
    return nbCrit;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 17 ms 24500 KB Output is correct
3 Correct 18 ms 24652 KB Output is correct
4 Correct 15 ms 24072 KB Output is correct
5 Correct 15 ms 24368 KB Output is correct
6 Correct 17 ms 24652 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24572 KB Output is correct
9 Correct 18 ms 24620 KB Output is correct
10 Correct 17 ms 24652 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 92200 KB Output is correct
2 Correct 1612 ms 128900 KB Output is correct
3 Correct 1538 ms 151128 KB Output is correct
4 Correct 1357 ms 154808 KB Output is correct
5 Correct 1403 ms 154888 KB Output is correct
6 Correct 1331 ms 153224 KB Output is correct
7 Correct 1496 ms 150356 KB Output is correct
8 Correct 2396 ms 146596 KB Output is correct
9 Correct 2490 ms 154836 KB Output is correct
10 Correct 941 ms 153092 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 17 ms 24500 KB Output is correct
3 Correct 18 ms 24652 KB Output is correct
4 Correct 15 ms 24072 KB Output is correct
5 Correct 15 ms 24368 KB Output is correct
6 Correct 17 ms 24652 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24572 KB Output is correct
9 Correct 18 ms 24620 KB Output is correct
10 Correct 17 ms 24652 KB Output is correct
11 Correct 17 ms 24712 KB Output is correct
12 Correct 21 ms 25304 KB Output is correct
13 Incorrect 22 ms 25264 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 17 ms 24500 KB Output is correct
3 Correct 18 ms 24652 KB Output is correct
4 Correct 15 ms 24072 KB Output is correct
5 Correct 15 ms 24368 KB Output is correct
6 Correct 17 ms 24652 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24572 KB Output is correct
9 Correct 18 ms 24620 KB Output is correct
10 Correct 17 ms 24652 KB Output is correct
11 Correct 17 ms 24712 KB Output is correct
12 Correct 21 ms 25304 KB Output is correct
13 Incorrect 22 ms 25264 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 17 ms 24500 KB Output is correct
3 Correct 18 ms 24652 KB Output is correct
4 Correct 15 ms 24072 KB Output is correct
5 Correct 15 ms 24368 KB Output is correct
6 Correct 17 ms 24652 KB Output is correct
7 Correct 15 ms 24524 KB Output is correct
8 Correct 16 ms 24572 KB Output is correct
9 Correct 18 ms 24620 KB Output is correct
10 Correct 17 ms 24652 KB Output is correct
11 Correct 536 ms 92200 KB Output is correct
12 Correct 1612 ms 128900 KB Output is correct
13 Correct 1538 ms 151128 KB Output is correct
14 Correct 1357 ms 154808 KB Output is correct
15 Correct 1403 ms 154888 KB Output is correct
16 Correct 1331 ms 153224 KB Output is correct
17 Correct 1496 ms 150356 KB Output is correct
18 Correct 2396 ms 146596 KB Output is correct
19 Correct 2490 ms 154836 KB Output is correct
20 Correct 941 ms 153092 KB Output is correct
21 Correct 17 ms 24712 KB Output is correct
22 Correct 21 ms 25304 KB Output is correct
23 Incorrect 22 ms 25264 KB Output isn't correct
24 Halted 0 ms 0 KB -