#include <vector>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 5005;
const int X = 1005;
bool all = true;
bool bad = false;
bool bad2[X];
vector<int> big3;
vector<int> adj[X][N];
int p[X][N];
//int r[3][N];
bool second = false;
int n;
int getR(int x, int a)
{
if (p[x][a] == a)return a;
p[x][a] = getR(x, p[x][a]);
return p[x][a];
}
void join(int x, int a, int b)
{
a = getR(x, a);
b = getR(x, b);
if (a == b) return;
p[x][a] = b;
}
bool vis[N];
bool onSt[N];
vector<int> st;
vector<int> cycle;
void getCycle(int node, int par)
{
vis[node] = true;
onSt[node] = true;
st.push_back(node);
for (int next : adj[0][node])
{
if (next == par || (vis[next] && !onSt[next])) continue;
if (onSt[next])
{
auto it = st.rbegin();
while (*it != next)
{
cycle.push_back(*it);
it++;
}
cycle.push_back(next);
} else
{
getCycle(next, node);
}
}
st.pop_back();
onSt[node] = false;
}
void Init(int n_) {
n = n_;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < X; j++) p[j][i] = i;
}
}
void Link(int a, int b) {
if (bad) return;
if (big3.size() <= X - 1 && !big3.empty())
{
second = true;
int ok = 0;
for (int l = 1; l <= X - 1; l++)
{
if (bad2[l]) continue;
if (a == big3[l - 1] || b == big3[l - 1]) continue;
adj[l][a].push_back(b);
adj[l][b].push_back(a);
if (getR(l, a) == getR(l, b))
{
bad2[l] = true;
continue;
}
join(l, a, b);
for (int t = 0; t < 2; t++)
{
swap(a, b);
if (adj[l][a].size() >= 3)
{
bad2[l] = true;
continue;
}
}
ok += !bad2[l];
}
} else
{
adj[0] [a].push_back(b);
adj[0] [b].push_back(a);
if (getR(0, a) == getR(0, b) && cycle.empty())
{
all = false;
getCycle(a, -1);
if (big3.empty()) big3 = cycle;
else
{
vector<int> n3;
for (int i : cycle)
{
for (int j : big3) if (i == j) n3.push_back(i);
}
big3 = n3;
}
}
join(0, a, b);
for (int t = 0; t < 2; t++)
{
swap(a, b);
if (adj[0] [a].size() >= 3)
{
all = false;
if (big3.empty())
{
big3.push_back(a);
if (adj[0][a].size() == 3)for (int i : adj[0] [a]) big3.push_back(i);
} else
{
vector<int> n3;
for (int i : big3)
{
bool good = false;
if (adj[0][a].size() == 3)for (int j : adj[0] [a]) if (j == i) good = true;
if (i == a) good = true;
if (good) n3.push_back(i);
}
big3 = n3;
}
}
}
if (big3.size() <= X - 1 && !big3.empty())
{
for (int l = 1; l <= X - 1; l++)
{
if (big3.size() < l)
{
bad2[l] = true;
} else
{
for (int i = 0; i < n; i++)
{
if (i == big3[l - 1]) continue;
for (int j : adj[0][i]) if (j != big3[l - 1])
{
adj[l][i].push_back(j);
join(l, i, j);
}
}
}
}
}
}
if (!all && big3.size() == 0)
{
bad = true;
}
}
int CountCritical() {
if (all) return n;
if (bad) return 0;
if (!second) return big3.size();
int res = 0;
for (int i = 1; i<= X; i++) res += !bad2[i];
return res;
}
Compilation message
rings.cpp: In function 'void Link(int, int)':
rings.cpp:171:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
171 | if (big3.size() < l)
| ~~~~~~~~~~~~^~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:205:47: warning: iteration 1004 invokes undefined behavior [-Waggressive-loop-optimizations]
205 | for (int i = 1; i<= X; i++) res += !bad2[i];
| ~~~~~~^
rings.cpp:205:22: note: within this loop
205 | for (int i = 1; i<= X; i++) res += !bad2[i];
| ~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
122860 KB |
Output is correct |
| 2 |
Incorrect |
110 ms |
138860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1885 ms |
262144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
122860 KB |
Output is correct |
| 2 |
Incorrect |
110 ms |
138860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
122860 KB |
Output is correct |
| 2 |
Incorrect |
110 ms |
138860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
122860 KB |
Output is correct |
| 2 |
Incorrect |
110 ms |
138860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
