Submission #1041089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041089		jer033	Parachute rings (IOI12_rings)	C++17	100 / 100	552 ms	244972 KiB

rings

#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);
                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 (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:257:33: warning: unused variable 'x' [-Wunused-variable]
  257 |                             int x = sys_1.CreateLink(i, j);
      |                                 ^
rings.cpp:259:33: warning: unused variable 'x' [-Wunused-variable]
  259 |                             int x = sys_2.CreateLink(i, j);
      |                                 ^
rings.cpp:261:33: warning: unused variable 'x' [-Wunused-variable]
  261 |                             int x = sys_3.CreateLink(i, j);
      |                                 ^
rings.cpp:263:33: warning: unused variable 'x' [-Wunused-variable]
  263 |                             int x = sys_4.CreateLink(i, j);
      |                                 ^
rings.cpp:273:17: warning: unused variable 'x' [-Wunused-variable]
  273 |             int x = sys_1.CreateLink(i, j);
      |                 ^
rings.cpp:275:17: warning: unused variable 'x' [-Wunused-variable]
  275 |             int x = sys_2.CreateLink(i, j);
      |                 ^
rings.cpp:277:17: warning: unused variable 'x' [-Wunused-variable]
  277 |             int x = sys_3.CreateLink(i, j);
      |                 ^
rings.cpp:279:17: warning: unused variable 'x' [-Wunused-variable]
  279 |             int x = sys_4.CreateLink(i, j);
      |                 ^
rings.cpp: In member function 'int LinkedIn::CCreateLink(int, int)':
rings.cpp:164:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |                     chains[chains[B]] = newchains2B;
rings.cpp:124:42: warning: 'next_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |                         visited[next_node] = 1;
      |                                          ^
rings.cpp: In function 'void Link(int, int)':
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~
rings.cpp:76:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |                     chains[chains[B]] = newchains2B;
rings.cpp:48:34: note: 'newchains2B' was declared here
   48 |                 int newchains2A, newchains2B;
      |                                  ^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31