oj.uz

답안 #1041087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041087 2024-08-01T15:17:08 Z jer033 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 560 ms 244856 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
int curr_answer;
bool second_stage;

class LinkedIn{
public:
    vector<vector<int>> edges;
    vector<int> chains;
    //value encoded: other endpoint of chain (itself if 0 connections), or -1 if it has 2 connections
    vector<int> degree;
    int cycle_count;
    int cycle_size;
    bool three_exists;

    LinkedIn(int N_)
    {
        edges = vector<vector<int>> (N_);
        chains = vector<int> (N_);
        for (int i=0; i<N_; i++)
            chains[i] = i;
        degree = vector<int> (N_, 0);
        
        cycle_count = 0;
        cycle_size = 0;
        three_exists = 0;
    };

    int CreateLink(int A, int B)
    {
        degree[A]++;
        degree[B]++;
        
        if ((chains[A]>=0) and (chains[B]>=0))
        {
            if ((chains[A]==B) and (chains[B]==A))
            {
                cycle_count++;
                cycle_count = min(cycle_count, 2);
                if (cycle_count == 1)
                {
                    vector<int> visited(N, 0);
                    visited[A] = 1;
                    int curr = A;
                    cycle_size = 1;
                    while (curr!=B)
                    {
                        int next_node;
                        for (int c: edges[curr])
                            if (visited[c]==0)
                                next_node = c;
                        visited[next_node] = 1;
                        curr = next_node;
                        cycle_size++;
                    }
                    //cout << "A cycle of size " << cycle_size << " has been formed\n";
                }
                chains[A] = -1;
                chains[B] = -1;
            }
            else
            {
                int newchainsA, newchainsB;
                int newchains2A, newchains2B;
                if (chains[A]==A)
                    newchainsA = chains[B];
                else
                {
                    newchains2A = chains[B];
                    newchainsA = -1;
                }
                if (chains[B]==B)
                    newchainsB = chains[A];
                else
                {
                    newchains2B = chains[A];
                    newchainsB = -1;
                }

                if (chains[A]==A)
                    chains[A] = newchainsA;
                else
                {
                    chains[chains[A]] = newchains2A;
                    chains[A] = newchainsA;
                }

                if (chains[B]==B)
                    chains[B] = newchainsB;
                else
                {
                    chains[chains[B]] = newchains2B;
                    chains[B] = newchainsB;
                }
            }
        }
        else{
            three_exists = 1;
        }

        if (degree[A]>=3)
            three_exists = 1;
        if (degree[B]>=3)
            three_exists = 1;

        /*for (int i=0; i<N; i++)
            cout << chains[i] << ' ';
        cout << '\n';*/

        if (three_exists)
            return 3;
        else if (cycle_count > 0)
            return min(cycle_count, 2);
        return 0;
    };

    int CCreateLink(int A, int B)
    {
        degree[A]++;
        degree[B]++;
        
        if ((chains[A]>=0) and (chains[B]>=0))
        {
            if ((chains[A]==B) and (chains[B]==A))
            {
                cycle_count++;
                cycle_count = min(cycle_count, 2);
                if (cycle_count == 1)
                {
                    vector<int> visited(N, 0);
                    visited[A] = 1;
                    int curr = A;
                    cycle_size = 1;
                    while (curr!=B)
                    {
                        int next_node;
                        for (int c: edges[curr])
                            if (visited[c]==0)
                                next_node = c;
                        visited[next_node] = 1;
                        curr = next_node;
                        cycle_size++;
                    }
                    //cout << "A cycle of size " << cycle_size << " has been formed\n";
                }
                chains[A] = -1;
                chains[B] = -1;
            }
            else
            {
                int newchainsA, newchainsB;
                int newchains2A, newchains2B;
                if (chains[A]==A)
                    newchainsA = chains[B];
                else
                {
                    newchains2A = chains[B];
                    newchainsA = -1;
                }
                if (chains[B]==B)
                    newchainsB = chains[A];
                else
                {
                    newchains2B = chains[A];
                    newchainsB = -1;
                }

                if (chains[A]==A)
                    chains[A] = newchainsA;
                else
                {
                    chains[chains[A]] = newchains2A;
                    chains[A] = newchainsA;
                }

                if (chains[B]==B)
                    chains[B] = newchainsB;
                else
                {
                    chains[chains[B]] = newchains2B;
                    chains[B] = newchainsB;
                }
            }
        }
        else{
            three_exists = 1;
        }

        edges[A].push_back(B);
        edges[B].push_back(A);

        if (degree[A]>=3)
            three_exists = 1;
        if (degree[B]>=3)
            three_exists = 1;

        /*for (int i=0; i<N; i++)
            cout << chains[i] << ' ';
        cout << '\n';*/

        if (three_exists)
            return 3;
        else if (cycle_count > 0)
            return min(cycle_count, 2);
        return 0;
    };

    int answer()
    {
        if (cycle_count>=2)
            return 0;
        if (cycle_count==1)
            return cycle_size;
        return N;
    }

    int answer_2()
    {
        if (three_exists)
            return 0;
        if (cycle_count >= 1)
            return 0;
        return 1;
    }
};

int c1, c2, c3, c4;
LinkedIn sys_0(0);
LinkedIn sys_1(0);
LinkedIn sys_2(0);
LinkedIn sys_3(0);
LinkedIn sys_4(0);

void Init(int N_) {
    N = N_;
    curr_answer = N_;
    sys_0 = LinkedIn(N_);
    second_stage = 0;
}

void Link(int A, int B) {
    if (second_stage == 0)
    {
        int result = sys_0.CCreateLink(A, B);
        if (result != 3)
        {
            curr_answer = sys_0.answer();
        }
        else
        {
            second_stage = 1;
            vector<vector<int>> con = sys_0.edges;
            vector<int> deg = sys_0.degree;
            int center;
            if (deg[A] == 3)
                center = A;
            else
                center = B;
            c1 = center;
            c2 = con[center][0];
            c3 = con[center][1];
            c4 = con[center][2];
            sys_1 = LinkedIn(N);
            sys_2 = LinkedIn(N);
            sys_3 = LinkedIn(N);
            sys_4 = LinkedIn(N);
            //cout << c1 << c2 << c3 << c4 << '\n';
            for (int i=0; i<N; i++)
                for (int j: con[i])
                    if (i<j)
                    {
                        if ((i!=c1) and (j!=c1))
                            int x = sys_1.CreateLink(i, j);
                        if ((i!=c2) and (j!=c2))
                            int x = sys_2.CreateLink(i, j);
                        if ((i!=c3) and (j!=c3))
                            int x = sys_3.CreateLink(i, j);
                        if ((i!=c4) and (j!=c4))
                            int x = sys_4.CreateLink(i, j);
                    }
            curr_answer = sys_1.answer_2() + sys_2.answer_2() + sys_3.answer_2() + sys_4.answer_2();
        }
    }
    else
    {
        int i = A;
        int j = B;
        if ((i!=c1) and (j!=c1))
            int x = sys_1.CreateLink(i, j);
        if ((i!=c2) and (j!=c2))
            int x = sys_2.CreateLink(i, j);
        if ((i!=c3) and (j!=c3))
            int x = sys_3.CreateLink(i, j);
        if ((i!=c4) and (j!=c4))
            int x = sys_4.CreateLink(i, j);
                    
        curr_answer = sys_1.answer_2() + sys_2.answer_2() + sys_3.answer_2() + sys_4.answer_2();
    }
}

int CountCritical() {
    return curr_answer;
}

/*int main()
{
    Init(1'000'000);
    for (int i=0; i<50'000; i++)
    {
        Link(i, i+1);
    }
    Link(76892, 291238);
    Link(4, 100);
    cout << CountCritical() << '\n';
}*/

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:275:33: warning: unused variable 'x' [-Wunused-variable]
  275 |                             int x = sys_1.CreateLink(i, j);
      |                                 ^
rings.cpp:277:33: warning: unused variable 'x' [-Wunused-variable]
  277 |                             int x = sys_2.CreateLink(i, j);
      |                                 ^
rings.cpp:279:33: warning: unused variable 'x' [-Wunused-variable]
  279 |                             int x = sys_3.CreateLink(i, j);
      |                                 ^
rings.cpp:281:33: warning: unused variable 'x' [-Wunused-variable]
  281 |                             int x = sys_4.CreateLink(i, j);
      |                                 ^
rings.cpp:291:17: warning: unused variable 'x' [-Wunused-variable]
  291 |             int x = sys_1.CreateLink(i, j);
      |                 ^
rings.cpp:293:17: warning: unused variable 'x' [-Wunused-variable]
  293 |             int x = sys_2.CreateLink(i, j);
      |                 ^
rings.cpp:295:17: warning: unused variable 'x' [-Wunused-variable]
  295 |             int x = sys_3.CreateLink(i, j);
      |                 ^
rings.cpp:297:17: warning: unused variable 'x' [-Wunused-variable]
  297 |             int x = sys_4.CreateLink(i, j);
      |                 ^
rings.cpp: In function 'int LinkedIn::CreateLink(int, int)':
rings.cpp:94:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |                     chains[chains[B]] = newchains2B;
rings.cpp:54:42: warning: 'next_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |                         visited[next_node] = 1;
      |                                          ^
rings.cpp: In member function 'int LinkedIn::CCreateLink(int, int)':
rings.cpp:182:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
  182 |                     chains[chains[B]] = newchains2B;
rings.cpp:142:42: warning: 'next_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |                         visited[next_node] = 1;
      |                                          ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 32852 KB Output is correct
2 Correct 336 ms 175400 KB Output is correct
3 Correct 301 ms 185168 KB Output is correct
4 Correct 423 ms 66896 KB Output is correct
5 Correct 420 ms 66896 KB Output is correct
6 Correct 495 ms 65704 KB Output is correct
7 Correct 261 ms 185428 KB Output is correct
8 Correct 490 ms 224852 KB Output is correct
9 Correct 560 ms 244856 KB Output is correct
10 Correct 275 ms 65104 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Runtime error 2 ms 2648 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Runtime error 2 ms 2648 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 135 ms 32852 KB Output is correct
12 Correct 336 ms 175400 KB Output is correct
13 Correct 301 ms 185168 KB Output is correct
14 Correct 423 ms 66896 KB Output is correct
15 Correct 420 ms 66896 KB Output is correct
16 Correct 495 ms 65704 KB Output is correct
17 Correct 261 ms 185428 KB Output is correct
18 Correct 490 ms 224852 KB Output is correct
19 Correct 560 ms 244856 KB Output is correct
20 Correct 275 ms 65104 KB Output is correct
21 Runtime error 2 ms 2648 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -