이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
const int mxN = 1e3+10;
vector<int> adj[mxN];
int p[mxN], root[mxN];
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
void uni(int x, int y) {
x = get(x); y = get(y);
if(x == y) return ;
if(p[x] > p[y]) swap(x, y);
p[x] += p[y];
p[y] = x;
}
bool same(int a, int b) {
return get(a) == get(b);
}
int construct(vector<vector<int>> P) {
int n = P.size();
for(int i = 0; i < n; i++) {
p[i] = -1;
root[i] = i;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(P[i][j] == 3) return 0;
if(P[i][j] == 1 && !same(i, j)) {
adj[i].push_back(j);
adj[j].push_back(i);
uni(i, j);
}
}
}
bool pos = true;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(P[i][j] == 1 && !same(i, j)) pos = false;
else if(P[i][j] == 2 && same(i, j)) pos = false;
else if(!P[i][j] && same(i, j)) pos = false;
}
}
for(int i = 0; i < n; i++) {
set<int> s;
for(int j = 0; j < n; j++) {
if(P[i][j] == 2 && !same(i, j)) {
s.insert(get(j));
}
}
if(s.empty()) continue;
if(s.size() == 1) {
pos = false;
break;
}
vector<int> v; for(auto it : s) v.push_back(it);
for(int i = 0; i+1 < v.size(); i++) {
int a = root[get(v[i])], b = root[get(v[i+1])];
adj[a].push_back(b);
adj[b].push_back(a);
}
int x = root[get(i)];
adj[x].push_back(root[v[0]]);
adj[root[v[0]]].push_back(x);
adj[x].push_back(root[v.back()]);
adj[v.back()].push_back(x);
for(int i = 0; i < v.size(); i++) {
uni(x, v[i]);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(!P[i][j] && same(i, j)) pos = false;
}
}
if(!pos) return 0;
vector<vector<int>> ans(n, vector<int>(n));
for(int i = 0; i < n; i++) {
for(auto it : adj[i]) {
ans[i][it] = ans[it][i] = 1;
}
}
build(ans);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i+1 < v.size(); i++) {
| ~~~~^~~~~~~~~~
supertrees.cpp:75:26: 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(); 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... |