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