#include <bits/stdc++.h>
#define pb push_back
//#define DEBUGGING
using namespace std;
void __print(int i) { cerr << i; }
template<typename T>
void __print(T& t) { cerr << "{"; int f = 0; for (auto& i : t) { cerr << (f++ ? ", " : ""); __print(i); } cerr << "}"; }
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) cerr <<"[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...) 42
#endif
struct Node
{
int head;
int tail;
int size;
int nxt;
Node(int i) : head(i), tail(i), size(1), nxt(-1) {}
Node() : Node(-1) {}
};
constexpr static int MXN = 1e6;
int n;
vector<int> p;
vector<int> g[MXN];
Node node[MXN];
void merge(int a, int b);
void Init(int N_)
{
n = N_;
for (int i = 0; i < n; i++)
{
node[i] = Node(i);
p.pb(i);
}
}
void check(int node)
{
if (g[node].size() <= 2 || g[node].size() >= 5)
return;
vector<int> p_new;
if (g[node].size() == 3)
for (int i : p)
if (i == node || find(g[node].begin(), g[node].end(), i) != g[node].end())
p_new.pb(i);
if (g[node].size() == 4)
for (int i : p)
if (i == node)
p_new.pb(i);
p = p_new;
}
vector<int> current_a;
bitset<MXN> visited;
int counter = 0;
bool dfs(int node, int target)
{
if (node == target)
return true;
bool valid = false;
visited[node] = true;
for (int c : g[node])
{
if (!visited[c] && dfs(c, target))
{
debug(node, c);
valid = true;
}
}
if (valid)
current_a.pb(node);
return valid;
}
void check(int a, int b)
{
visited.reset();
counter++;
visited[a] = true;
for (int i : g[a])
if (i != b)
dfs(i, b);
current_a.pb(a);
current_a.pb(b);
sort(current_a.begin(), current_a.begin());
int i = 0, j = 0;
vector<int> new_p;
while (i < current_a.size() && j < p.size())
{
if (current_a[i] == p[j])
{
new_p.pb(current_a[i++]);
j++;
}
else if (current_a[i] > p[j])
{
j++;
}
else
{
i++;
}
}
p = new_p;
}
void Link(int a, int b)
{
g[a].pb(b);
g[b].pb(a);
check(a);
check(b);
if (node[a].head == node[b].head && counter <= 3)
check(a, b);
else if (node[a].head == node[b].head)
p.clear();
else
merge(node[a].head, node[b].head);
}
int CountCritical()
{
debug(p);
return p.size();
}
void merge(int a, int b)
{
if (node[a].size < node[b].size) swap(a, b);
node[a].size += node[b].size;
node[node[a].tail].nxt = b;
node[a].tail = node[b].tail;
for (;b != -1; b = node[b].nxt)
node[b].head = a;
}
Compilation message
rings.cpp: In function 'bool dfs(int, int)':
rings.cpp:21:21: warning: statement has no effect [-Wunused-value]
21 | #define debug(x...) 42
| ^~
rings.cpp:87:25: note: in expansion of macro 'debug'
87 | debug(node, c);
| ^~~~~
rings.cpp: In function 'void check(int, int)':
rings.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while (i < current_a.size() && j < p.size())
| ~~^~~~~~~~~~~~~~~~~~
rings.cpp:109:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while (i < current_a.size() && j < p.size())
| ~~^~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:21:21: warning: statement has no effect [-Wunused-value]
21 | #define debug(x...) 42
| ^~
rings.cpp:145:9: note: in expansion of macro 'debug'
145 | debug(p);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
17 ms |
39592 KB |
Output is correct |
| 3 |
Correct |
17 ms |
39608 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
39496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
64632 KB |
Output is correct |
| 2 |
Correct |
720 ms |
78252 KB |
Output is correct |
| 3 |
Correct |
807 ms |
83344 KB |
Output is correct |
| 4 |
Incorrect |
1002 ms |
88152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
17 ms |
39592 KB |
Output is correct |
| 3 |
Correct |
17 ms |
39608 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
39496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
17 ms |
39592 KB |
Output is correct |
| 3 |
Correct |
17 ms |
39608 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
39496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
17 ms |
39592 KB |
Output is correct |
| 3 |
Correct |
17 ms |
39608 KB |
Output is correct |
| 4 |
Incorrect |
16 ms |
39496 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
