#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;
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
