이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<vector>
using namespace std;
const int dim = 1000005;
int n, nr3, nr4, m, num, nrcomp, nrcic, np;
int r[dim], g[dim], viz[dim], t[dim], frst[dim], cic[dim], rp[dim], r2[20][dim], nrc[20], nnod[20];
pair<int, int> w[dim];
vector<int> v[dim], g3, g4;
int rad(int x){
int aux, y = x;
while(r[x] > 0){
x = r[x];
}
while(r[y] > 0){
aux = r[y];
r[y] = x;
y = aux;
}
return x;
}
void uneste(int i, int x, int y){
if(x == nnod[i] || y == nnod[i]){
return;
}
int ax = x, ay = y, aux;
while(r2[i][x] >= 0){
x = r2[i][x];
}
while(r2[i][y] >= 0){
y = r2[i][y];
}
while(r2[i][ax] > 0){
aux = r2[i][ax];
r2[i][ax] = x;
ax = aux;
}
while(r2[i][ay] > 0){
aux = r2[i][ay];
r2[i][ay] = y;
ay = aux;
}
if(x != y){
nrc[i]++;
if(r2[i][x] > r2[i][y]){
r2[i][x] += r2[i][y];
r2[i][y] = x;
}
else{
r2[i][y] += r2[i][x];
r2[i][x] = y;
}
}
}
void update(int nod){
if(rp[nod] == 0 && g3.size() < 4 && g4.size() == 0){
np++;
rp[nod] = np;
nnod[np] = nod;
for(int i = 1; i <= m; i++){
uneste(np, w[i].first, w[i].second);
}
}
}
void upd(int nod){
if(g[nod] == 4){
nr3--;
nr4++;
g4.push_back(nod);
}
else if(g[nod] == 3){
nr3++;
g3.push_back(nod);
update(nod);
for(int i = 0; i < v[nod].size(); i++){
frst[ v[nod][i] ] = nod;
update(v[nod][i]);
}
}
}
int verif(int nod){
if(m - g[nod] != nrc[ rp[nod] ] ){
return 0;
}
int i, n3 = 0;
if(g[nod] == 3){
n3++;
}
for(int i = 0; i < v[nod].size(); i++){
if(g[ v[nod][i] ] == 3){
n3++;
}
}
if(n3 != nr3){
return 0;
}
return 1;
}
void Init(int N) {
n = N;
for(int i = 0; i < n; i++){
r[i] = -1;
for(int ii = 1; ii <= 18; ii++){
r2[ii][i] = -1;
}
}
}
static void dfs(int nod, int tt){
t[nod] = tt;
for(int i = 0; i < v[nod].size(); i++){
if(v[nod][i] != tt){
dfs(v[nod][i], nod);
}
}
}
void Link(int x, int y) {
int r1, r2, nod;
g[x]++;
g[y]++;
if(g[x] == 3){
frst[y] = x;
update(y);
}
if(g[y] == 3){
frst[x] = y;
update(x);
}
upd(x);
upd(y);
r1 = rad(x);
r2 = rad(y);
m++;
if(r1 != r2){
if(r[r1] < r[r2]){
r[r1] += r[r2];
r[r2] = r1;
cic[r1] |= cic[r2];
}
else{
r[r2] += r[r1];
r[r1] = r2;
cic[r2] |= cic[r1];
swap(r1, r2);
}
}
else{
nrcic++;
if(nrcic == 1){
t[x] = -1;
dfs(x, -1);
nod = y;
while(nod != -1){
viz[nod] = 1;
nod = t[nod];
num++;
}
}
if(cic[r1] == 0){
nrcomp++;
cic[r1] = 1;
}
}
v[x].push_back(y);
v[y].push_back(x);
w[m] = make_pair(x, y);
for(int i = 1; i <= np; i++){
uneste(i, x, y);
}
}
int CountCritical() {
if(nr4 > 1){
return 0;
}
if(nr4 == 1){
return verif(g4[0]);
}
if(nr3 > 3){
return 0;
}
if(nr3 != 0){
int nr = 0;
for(int i = 0; i < nr3; i++){
nr += verif(g3[i]);
int nod = g3[i];
for(int j = 0; j < v[nod].size(); j++){
if(frst[ v[nod][j] ] == nod && g[ v[nod][j] ] < 3){
nr += verif(v[nod][j]);
}
}
}
return nr;
}
if(nrcomp > 1){
return 0;
}
if(nrcomp == 1){
return num;
}
return n;
}
컴파일 시 표준 에러 (stderr) 메시지
rings.cpp: In function 'void upd(int)':
rings.cpp:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); i++){
~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int verif(int)':
rings.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); i++){
~~^~~~~~~~~~~~~~~
rings.cpp:83:9: warning: unused variable 'i' [-Wunused-variable]
int i, n3 = 0;
^
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); i++){
~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:186:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < v[nod].size(); j++){
~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |