이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "supertrees.h"
#define DIMN 1010
using namespace std;
int tt[DIMN] , c[DIMN];
vector <int> x , lnt , cycle;
int root (int x){
while (tt[x] > 0)
x = tt[x];
return x;
}
int construct(vector<vector<int>> p) {
int n = p.size() , i , ri , rj , j , caz , r;
vector<vector<int>> answer;
for (i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (i = 0 ; i < n ; i++)
tt[i] = -1;
for (i = 0 ; i < n ; i++){
c[i] = 0;
for (j = 0 ; j < n ; j++){
if (p[i][j] == 3)
return 0; /// ce teapa monumentala
if (p[i][j] && i != j){
c[i] = (c[i] | p[i][j]);
/// i si j in aceeasi componenta conexa
ri = root(i);
rj = root(j);
if (ri != rj){
if (tt[ri] < tt[rj]){
tt[ri] += tt[rj];
tt[rj] = ri;
}
else {
tt[rj] += tt[ri];
tt[ri] = rj;
}
}
}
}
}
for (i = 0 ; i < n ; i++){
for (j = 0 ; j < n ; j++){
if (!p[i][j]){
/// i si j in aceeasi componenta conexa
ri = root(i);
rj = root(j);
if (ri == rj) /// sunt in aceeasi cc si n ar trb sa fie
return 0;
}
}
}
for (r = 0 ; r < n ; r++){
if (tt[r] < 0){
x.clear();
for (i = 0 ; i < n ; i++){
if (root(i) == r)
x.push_back(i);
}
/// x = componenta conexa de acum
caz = 0;
for (i = 0 ; i < x.size() ; i++){
caz = (caz | c[x[i]]);
}
if (caz == 0)
continue;
else if (caz == 1){ /// lant
if (x.size() < 2)
return 0;
for (i = 0 ; i < x.size() - 1 ; i++){
answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1;
}
}
else if (caz == 2){ /// un ciclu simplu
if (x.size() < 3)
return 0;
for (i = 0 ; i < x.size() - 1 ; i++){
answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1;
}
answer[x[0]][x.back()] = answer[x.back()][x[0]] = 1;
}
else { /// cazul cand sunt si 1 si 2
cycle.clear();
lnt.clear();
int ok = 0;
for (i = 0 ; i < x.size() ; i++){
if (c[x[i]] == 2){
cycle.push_back(x[i]);
}
else if (c[x[i]] == 1)
return 0;
else {
if (!ok)
cycle.push_back(x[i]);
else lnt.push_back(x[i]);
ok = 1;
}
}
if (cycle.size() < 3)
return 0;
if (ok == 1 && lnt.size() == 0)
return 0;
for (i = 0 ; i < lnt.size() - 1 ; i++){
answer[lnt[i]][lnt[i + 1]] = answer[lnt[i + 1]][lnt[i]] = 1;
}
for (i = 0 ; i < cycle.size() - 1 ; i++){
answer[cycle[i]][cycle[i + 1]] = answer[cycle[i + 1]][cycle[i]] = 1;
}
answer[cycle[0]][cycle.back()] = answer[cycle.back()][cycle[0]] = 1;
answer[cycle[0]][lnt[0]] = answer[lnt[0]][cycle[0]] = 1;
}
}
}
build(answer);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:98:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (i = 0 ; i < x.size() ; i++){
| ~~^~~~~~~~~~
supertrees.cpp:109:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (i = 0 ; i < x.size() - 1 ; i++){
| ~~^~~~~~~~~~~~~~
supertrees.cpp:119:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (i = 0 ; i < x.size() - 1 ; i++){
| ~~^~~~~~~~~~~~~~
supertrees.cpp:131:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (i = 0 ; i < x.size() ; i++){
| ~~^~~~~~~~~~
supertrees.cpp:151:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (i = 0 ; i < lnt.size() - 1 ; i++){
| ~~^~~~~~~~~~~~~~~~
supertrees.cpp:156:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for (i = 0 ; i < cycle.size() - 1 ; i++){
| ~~^~~~~~~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |