oj.uz

Submission #433056

# Submission time Handle Problem Language Result Execution time Memory
433056 2021-06-18T19:21:27 Z someone Parachute rings (IOI12_rings) C++14
37 / 100
 2542 ms 165080 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]);
        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;
        if(d > 2)
            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 16 ms 24012 KB Output is correct
2 Correct 16 ms 24636 KB Output is correct
3 Correct 17 ms 24692 KB Output is correct
4 Correct 15 ms 24140 KB Output is correct
5 Correct 16 ms 24396 KB Output is correct
6 Correct 18 ms 24644 KB Output is correct
7 Correct 16 ms 24524 KB Output is correct
8 Correct 16 ms 24524 KB Output is correct
9 Correct 18 ms 24696 KB Output is correct
10 Correct 20 ms 24848 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 99080 KB Output is correct
2 Correct 1697 ms 138684 KB Output is correct
3 Correct 1590 ms 160908 KB Output is correct
4 Correct 1394 ms 164932 KB Output is correct
5 Correct 1428 ms 165036 KB Output is correct
6 Correct 1344 ms 163464 KB Output is correct
7 Correct 1521 ms 160324 KB Output is correct
8 Correct 2511 ms 156580 KB Output is correct
9 Correct 2542 ms 165080 KB Output is correct
10 Correct 949 ms 163400 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Correct 16 ms 24636 KB Output is correct
3 Correct 17 ms 24692 KB Output is correct
4 Correct 15 ms 24140 KB Output is correct
5 Correct 16 ms 24396 KB Output is correct
6 Correct 18 ms 24644 KB Output is correct
7 Correct 16 ms 24524 KB Output is correct
8 Correct 16 ms 24524 KB Output is correct
9 Correct 18 ms 24696 KB Output is correct
10 Correct 20 ms 24848 KB Output is correct
11 Correct 18 ms 24640 KB Output is correct
12 Correct 26 ms 25420 KB Output is correct
13 Incorrect 23 ms 25388 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Correct 16 ms 24636 KB Output is correct
3 Correct 17 ms 24692 KB Output is correct
4 Correct 15 ms 24140 KB Output is correct
5 Correct 16 ms 24396 KB Output is correct
6 Correct 18 ms 24644 KB Output is correct
7 Correct 16 ms 24524 KB Output is correct
8 Correct 16 ms 24524 KB Output is correct
9 Correct 18 ms 24696 KB Output is correct
10 Correct 20 ms 24848 KB Output is correct
11 Correct 18 ms 24640 KB Output is correct
12 Correct 26 ms 25420 KB Output is correct
13 Incorrect 23 ms 25388 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Correct 16 ms 24636 KB Output is correct
3 Correct 17 ms 24692 KB Output is correct
4 Correct 15 ms 24140 KB Output is correct
5 Correct 16 ms 24396 KB Output is correct
6 Correct 18 ms 24644 KB Output is correct
7 Correct 16 ms 24524 KB Output is correct
8 Correct 16 ms 24524 KB Output is correct
9 Correct 18 ms 24696 KB Output is correct
10 Correct 20 ms 24848 KB Output is correct
11 Correct 551 ms 99080 KB Output is correct
12 Correct 1697 ms 138684 KB Output is correct
13 Correct 1590 ms 160908 KB Output is correct
14 Correct 1394 ms 164932 KB Output is correct
15 Correct 1428 ms 165036 KB Output is correct
16 Correct 1344 ms 163464 KB Output is correct
17 Correct 1521 ms 160324 KB Output is correct
18 Correct 2511 ms 156580 KB Output is correct
19 Correct 2542 ms 165080 KB Output is correct
20 Correct 949 ms 163400 KB Output is correct
21 Correct 18 ms 24640 KB Output is correct
22 Correct 26 ms 25420 KB Output is correct
23 Incorrect 23 ms 25388 KB Output isn't correct
24 Halted 0 ms 0 KB -