#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
if (_split)
cerr << ", ";
cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
cerr << '[';
for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
vector<int> deg, rt, stk, ring;
vector<int> v;
vector<vector<int>> g;
vector<bool> vis;
bool fail, first;
int n;
int find(int i) {
return rt[i] = rt[i] == i ? i : find(rt[i]);
}
void dfs(int i, int p) {
vis[i] = true;
stk.push_back(i);
for (int j : g[i])
if (j != p) {
if (!vis[j])
dfs(j, i);
else {
while (stk.back() != j)
ring.push_back(stk.back()), stk.pop_back();
ring.push_back(j);
return;
}
if (!ring.empty())
return;
}
}
void upd(vector<int> tmp) {
if (fail)
return;
if (v.empty()) {
v = tmp;
return;
}
for (int i = 0; i < v.size(); ) {
bool find = false;
for (int j : tmp)
if (v[i] == j) {
find = true;
}
if (!find)
swap(v[i], v.back()), v.pop_back();
else
++i;
}
if (v.empty())
fail = true;
}
void Init(int N) {
deg.assign(N, 0);
rt.resize(N);
vis.assign(n, false);
g.assign(n, vector<int>());
fail = false, first = true;
n = N;
}
void Link(int x, int y) {
if (fail)
return;
++deg[x], ++deg[y];
g[x].push_back(y), g[y].push_back(x);
if (deg[x] == 4) {
vector<int> tmp(1, x);
upd(tmp);
}
else if (deg[x] == 3) {
vector<int> tmp = g[x];
tmp.push_back(x);
upd(tmp);
}
if (fail)
return;
if (deg[y] == 4) {
vector<int> tmp(1, y);
upd(tmp);
}
else if (deg[y] == 3) {
vector<int> tmp = g[y];
tmp.push_back(y);
upd(tmp);
}
if (fail)
return;
if (find(x) == find(y)) {
if (first) {
first = false;
dfs(x, -1);
upd(ring);
}
}
else {
rt[find(x)] = find(y);
}
}
int CountCritical() {
if (fail)
return 0;
if (v.empty())
return n;
return v.size();
}
Compilation message
rings.cpp: In function 'void upd(std::vector<int>)':
rings.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < v.size(); ) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
8748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
