oj.uz

Submission #361875

# Submission time Handle Problem Language Result Execution time Memory
361875 2021-01-31T19:11:24 Z idk321 Parachute rings (IOI12_rings) C++11
20 / 100
 1873 ms 262144 KB 

#include <vector>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;



const int N = 5005;
const int X = 1005;
bool all = true;
bool bad = false;
bool bad2[X];
vector<int> big3;
vector<int> adj[X][N];
int p[X][N];
//int r[3][N];
bool second = false;

int n;

int getR(int x, int a)
{
    if (p[x][a] == a)return a;
    p[x][a] = getR(x, p[x][a]);
    return p[x][a];
}

void join(int x, int a, int b)
{
    a = getR(x, a);
    b = getR(x, b);
    if (a == b) return;
    p[x][a] = b;
}


bool vis[N];
bool onSt[N];
vector<int> st;
vector<int> cycle;
void getCycle(int node, int par)
{
    vis[node] = true;
    onSt[node] = true;
    st.push_back(node);
    for (int next : adj[0][node])
    {
        if (next == par || (vis[next] && !onSt[next])) continue;
        if (onSt[next])
        {
            auto it = st.rbegin();
            while (*it != next)
            {
                cycle.push_back(*it);
                it++;
            }
            cycle.push_back(next);
        } else
        {
            getCycle(next, node);
        }
    }

    st.pop_back();
    onSt[node] = false;
}

void Init(int n_) {
    n = n_;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < X; j++) p[j][i] = i;
    }

}

void Link(int a, int b) {
    if (bad) return;

    if (big3.size() <= X - 1 && !big3.empty())
    {
        second = true;
        int ok = 0;
        for (int l = 1; l <= X - 1; l++)
        {
            if (bad2[l]) continue;
            if (a == big3[l - 1] || b == big3[l - 1]) continue;
            adj[l][a].push_back(b);
            adj[l][b].push_back(a);
            if (getR(l, a) == getR(l, b))
            {

                bad2[l] = true;
                continue;
            }
            join(l, a, b);

            for (int t = 0; t < 2; t++)
            {
                swap(a, b);

                if (adj[l][a].size() >= 3)
                {
                    bad2[l] = true;
                    continue;
                }
            }
            ok += !bad2[l];
        }

    } else
    {

        adj[0] [a].push_back(b);
        adj[0] [b].push_back(a);
        if (getR(0, a) == getR(0, b) && cycle.empty())
        {
            all = false;


            getCycle(a, -1);

            if (big3.empty()) big3 = cycle;
            else
            {
                vector<int> n3;

                for (int i : cycle)
                {
                    for (int j : big3) if (i == j) n3.push_back(i);
                }

                big3 = n3;
            }
        }

        join(0, a, b);
        for (int t = 0; t < 2; t++)
        {
            swap(a, b);
            if (adj[0] [a].size() >= 3)
            {
                all = false;
                if (big3.empty())
                {
                    big3.push_back(a);
                    if (adj[0][a].size() == 3)for (int i : adj[0] [a]) big3.push_back(i);
                } else
                {
                    vector<int> n3;
                    for (int i : big3)
                    {
                        bool good = false;
                        if (adj[0][a].size() == 3)for (int j : adj[0] [a]) if (j == i) good = true;
                        if (i == a) good = true;
                        if (good) n3.push_back(i);
                    }
                    big3 = n3;
                }

            }
        }

        if (big3.size() <= X - 1 && !big3.empty())
        {
            for (int l = 1; l <= X - 1; l++)
            {
                if (big3.size() < l)
                {
                    bad2[l] = true;
                } else
                {
                    for (int i = 0; i < n; i++)
                    {
                        if (i == big3[l - 1]) continue;
                        for (int j : adj[0][i]) if (j != big3[l - 1])
                        {
                            adj[l][i].push_back(j);
                            join(l, i, j);
                        }
                    }
                }
            }
        }
    }


    if (!all && big3.size() == 0)
    {
        bad = true;
    }

}

int CountCritical() {
    if (all) return n;
    if (bad) return 0;

    if (!second) return big3.size();

    int res = 0;
    for (int i = 1; i<= X - 1; i++) res += !bad2[i];
    return res;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:171:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  171 |                 if (big3.size() < l)
      |                     ~~~~~~~~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122988 KB Output is correct
2 Correct 108 ms 138732 KB Output is correct
3 Correct 113 ms 138604 KB Output is correct
4 Correct 103 ms 129644 KB Output is correct
5 Correct 103 ms 134636 KB Output is correct
6 Correct 110 ms 138732 KB Output is correct
7 Correct 106 ms 138220 KB Output is correct
8 Correct 128 ms 143340 KB Output is correct
9 Correct 112 ms 138860 KB Output is correct
10 Correct 112 ms 139116 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1873 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122988 KB Output is correct
2 Correct 108 ms 138732 KB Output is correct
3 Correct 113 ms 138604 KB Output is correct
4 Correct 103 ms 129644 KB Output is correct
5 Correct 103 ms 134636 KB Output is correct
6 Correct 110 ms 138732 KB Output is correct
7 Correct 106 ms 138220 KB Output is correct
8 Correct 128 ms 143340 KB Output is correct
9 Correct 112 ms 138860 KB Output is correct
10 Correct 112 ms 139116 KB Output is correct
11 Correct 112 ms 138860 KB Output is correct
12 Runtime error 292 ms 262144 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122988 KB Output is correct
2 Correct 108 ms 138732 KB Output is correct
3 Correct 113 ms 138604 KB Output is correct
4 Correct 103 ms 129644 KB Output is correct
5 Correct 103 ms 134636 KB Output is correct
6 Correct 110 ms 138732 KB Output is correct
7 Correct 106 ms 138220 KB Output is correct
8 Correct 128 ms 143340 KB Output is correct
9 Correct 112 ms 138860 KB Output is correct
10 Correct 112 ms 139116 KB Output is correct
11 Correct 112 ms 138860 KB Output is correct
12 Runtime error 292 ms 262144 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 122988 KB Output is correct
2 Correct 108 ms 138732 KB Output is correct
3 Correct 113 ms 138604 KB Output is correct
4 Correct 103 ms 129644 KB Output is correct
5 Correct 103 ms 134636 KB Output is correct
6 Correct 110 ms 138732 KB Output is correct
7 Correct 106 ms 138220 KB Output is correct
8 Correct 128 ms 143340 KB Output is correct
9 Correct 112 ms 138860 KB Output is correct
10 Correct 112 ms 139116 KB Output is correct
11 Runtime error 1873 ms 262144 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -