oj.uz

답안 #361856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361856 2021-01-31T18:39:36 Z idk321 낙하산 고리들 (IOI12_rings) C++11
0 / 100
 1135 ms 157940 KB 

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

const int N = 1000005;
bool all = true;
bool bad = false;
bool bad2[4];
vector<int> big3;
vector<int> adj[4][N];
int p[4][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];
deque<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 < 4; j++) p[j][i] = i;
    }

}

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

    if (big3.size() <= 3 && !big3.empty())
    {
        second = true;

        for (int l = 1; l <= 3; 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;
                }
            }
        }
    } else
    {

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

            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() <= 3 && !big3.empty())
        {
            for (int l = 1; l <= 3; 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<= 3; i++) res += !bad2[i];
    return res;
}

Compilation message

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

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94316 KB Output is correct
2 Correct 66 ms 94700 KB Output is correct
3 Correct 66 ms 94700 KB Output is correct
4 Incorrect 65 ms 94444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 453 ms 125732 KB Output is correct
2 Correct 1043 ms 157940 KB Output is correct
3 Correct 316 ms 123288 KB Output is correct
4 Incorrect 1135 ms 156648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94316 KB Output is correct
2 Correct 66 ms 94700 KB Output is correct
3 Correct 66 ms 94700 KB Output is correct
4 Incorrect 65 ms 94444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94316 KB Output is correct
2 Correct 66 ms 94700 KB Output is correct
3 Correct 66 ms 94700 KB Output is correct
4 Incorrect 65 ms 94444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 94316 KB Output is correct
2 Correct 66 ms 94700 KB Output is correct
3 Correct 66 ms 94700 KB Output is correct
4 Incorrect 65 ms 94444 KB Output isn't correct
5 Halted 0 ms 0 KB -