답안 #361871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361871	2021-01-31T19:00:13 Z	idk321	낙하산 고리들 (IOI12_rings)	C++11	컴파일 오류	0 ms	0 KB

rings

005;
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;

        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;
                }
            }
        }
    } 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 <= 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:1:1: error: expected unqualified-id before numeric constant
    1 | 005;
      | ^~~
rings.cpp:4:11: error: 'X' was not declared in this scope
    4 | bool bad2[X];
      |           ^
rings.cpp:5:1: error: 'vector' does not name a type
    5 | vector<int> big3;
      | ^~~~~~
rings.cpp:6:1: error: 'vector' does not name a type
    6 | vector<int> adj[X][N];
      | ^~~~~~
rings.cpp:7:7: error: 'X' was not declared in this scope
    7 | int p[X][N];
      |       ^
rings.cpp:7:10: error: 'N' was not declared in this scope
    7 | int p[X][N];
      |          ^
rings.cpp: In function 'int getR(int, int)':
rings.cpp:15:9: error: 'p' was not declared in this scope
   15 |     if (p[x][a] == a)return a;
      |         ^
rings.cpp:16:5: error: 'p' was not declared in this scope
   16 |     p[x][a] = getR(x, p[x][a]);
      |     ^
rings.cpp: In function 'void join(int, int, int)':
rings.cpp:25:5: error: 'p' was not declared in this scope
   25 |     p[x][a] = b;
      |     ^
rings.cpp: At global scope:
rings.cpp:29:10: error: 'N' was not declared in this scope
   29 | bool vis[N];
      |          ^
rings.cpp:30:11: error: 'N' was not declared in this scope
   30 | bool onSt[N];
      |           ^
rings.cpp:31:1: error: 'vector' does not name a type
   31 | vector<int> st;
      | ^~~~~~
rings.cpp:32:1: error: 'vector' does not name a type
   32 | vector<int> cycle;
      | ^~~~~~
rings.cpp: In function 'void getCycle(int, int)':
rings.cpp:35:5: error: 'vis' was not declared in this scope
   35 |     vis[node] = true;
      |     ^~~
rings.cpp:36:5: error: 'onSt' was not declared in this scope
   36 |     onSt[node] = true;
      |     ^~~~
rings.cpp:37:5: error: 'st' was not declared in this scope; did you mean 'std'?
   37 |     st.push_back(node);
      |     ^~
      |     std
rings.cpp:38:21: error: 'adj' was not declared in this scope
   38 |     for (int next : adj[0][node])
      |                     ^~~
rings.cpp:46:17: error: 'cycle' was not declared in this scope
   46 |                 cycle.push_back(*it);
      |                 ^~~~~
rings.cpp:49:13: error: 'cycle' was not declared in this scope
   49 |             cycle.push_back(next);
      |             ^~~~~
rings.cpp: In function 'void Init(int)':
rings.cpp:64:29: error: 'X' was not declared in this scope
   64 |         for (int j = 0; j < X; j++) p[j][i] = i;
      |                             ^
rings.cpp:64:37: error: 'p' was not declared in this scope
   64 |         for (int j = 0; j < X; j++) p[j][i] = i;
      |                                     ^
rings.cpp: In function 'void Link(int, int)':
rings.cpp:72:9: error: 'big3' was not declared in this scope
   72 |     if (big3.size() <= X - 1 && !big3.empty())
      |         ^~~~
rings.cpp:72:24: error: 'X' was not declared in this scope
   72 |     if (big3.size() <= X - 1 && !big3.empty())
      |                        ^
rings.cpp:78:17: error: 'bad2' was not declared in this scope; did you mean 'bad'?
   78 |             if (bad2[l]) continue;
      |                 ^~~~
      |                 bad
rings.cpp:80:13: error: 'adj' was not declared in this scope
   80 |             adj[l][a].push_back(b);
      |             ^~~
rings.cpp:85:17: error: 'bad2' was not declared in this scope; did you mean 'bad'?
   85 |                 bad2[l] = true;
      |                 ^~~~
      |                 bad
rings.cpp:92:17: error: 'swap' was not declared in this scope
   92 |                 swap(a, b);
      |                 ^~~~
rings.cpp:96:21: error: 'bad2' was not declared in this scope; did you mean 'bad'?
   96 |                     bad2[l] = true;
      |                     ^~~~
      |                     bad
rings.cpp:104:9: error: 'adj' was not declared in this scope
  104 |         adj[0] [a].push_back(b);
      |         ^~~
rings.cpp:106:41: error: 'cycle' was not declared in this scope
  106 |         if (getR(0, a) == getR(0, b) && cycle.empty())
      |                                         ^~~~~
rings.cpp:116:17: error: 'vector' was not declared in this scope
  116 |                 vector<int> n3;
      |                 ^~~~~~
rings.cpp:116:24: error: expected primary-expression before 'int'
  116 |                 vector<int> n3;
      |                        ^~~
rings.cpp:120:52: error: 'n3' was not declared in this scope; did you mean 'n'?
  120 |                     for (int j : big3) if (i == j) n3.push_back(i);
      |                                                    ^~
      |                                                    n
rings.cpp:123:24: error: 'n3' was not declared in this scope; did you mean 'n'?
  123 |                 big3 = n3;
      |                        ^~
      |                        n
rings.cpp:130:13: error: 'swap' was not declared in this scope
  130 |             swap(a, b);
      |             ^~~~
rings.cpp:140:21: error: 'vector' was not declared in this scope
  140 |                     vector<int> n3;
      |                     ^~~~~~
rings.cpp:140:28: error: expected primary-expression before 'int'
  140 |                     vector<int> n3;
      |                            ^~~
rings.cpp:146:35: error: 'n3' was not declared in this scope; did you mean 'n'?
  146 |                         if (good) n3.push_back(i);
      |                                   ^~
      |                                   n
rings.cpp:148:28: error: 'n3' was not declared in this scope; did you mean 'n'?
  148 |                     big3 = n3;
      |                            ^~
      |                            n
rings.cpp:160:21: error: 'bad2' was not declared in this scope; did you mean 'bad'?
  160 |                     bad2[l] = true;
      |                     ^~~~
      |                     bad
rings.cpp:178:17: error: 'big3' was not declared in this scope
  178 |     if (!all && big3.size() == 0)
      |                 ^~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:189:25: error: 'big3' was not declared in this scope
  189 |     if (!second) return big3.size();
      |                         ^~~~
rings.cpp:192:41: error: 'bad2' was not declared in this scope; did you mean 'bad'?
  192 |     for (int i = 1; i<= 3; i++) res += !bad2[i];
      |                                         ^~~~
      |                                         bad