#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++;
}
}
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{ I WILL NOT PARSE THIS because the condition only fails when one of the terms is in the middle of a chain, so this whole function will return 3 }
edges[A].push_back(B);
edges[B].push_back(A);
if (degree[A]>=3)
three_exists = 1;
if (degree[B]>=3)
three_exists = 1;
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.CreateLink(A, B);
if (result != 3)
{
curr_answer = sys_0.answer();
}
else
{
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);
for (int i=0; i<N; i++)
for (int j: con[i])
if (i<j)
{
if ((i!=c1) and (j!=c1))
sys_1.CreateLink(i, j);
if ((i!=c2) and (j!=c2))
sys_2.CreateLink(i, j);
if ((i!=c3) and (j!=c3))
sys_3.CreateLink(i, j);
if ((i!=c4) and (j!=c4))
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))
sys_1.CreateLink(i, j);
if ((i!=c2) and (j!=c2))
sys_2.CreateLink(i, j);
if ((i!=c3) and (j!=c3))
sys_3.CreateLink(i, j);
if ((i!=c4) and (j!=c4))
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;
}
Compilation message
rings.cpp: In member function 'int LinkedIn::CreateLink(int, int)':
rings.cpp:93:39: warning: 'newchains2B' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | 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;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2817 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
39692 KB |
Output is correct |
| 2 |
Runtime error |
1041 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2817 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2817 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2817 ms |
2136 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
