이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j);i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
using namespace std;
struct dsu{
vector<int> p;
int n;
dsu(int _n){
p.resize(n, -1);
}
int find(int x){
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool sameSet(int u, int v){
return (find(u) == find(v));
}
bool join(int a, int b){
a = find(a); b = find(b);
if(a == b)
return false;
if(p[a] > p[b])
swap(a, b);
p[a] += p[b];
p[b] = a;
return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
REP(i, n){
REP(j, n){
if(p[i][j] == 3)
return 0;
}
}
vector<vector<int>> answer(n, vector<int>(n, 0));
dsu d(n);
REP(i, n){
REP(j, i){
if(p[i][j] == 1)
d.join(i, j);
}
}
REP(i, n){
if(d.find(i) != i){
int rp = d.find(i);
answer[rp][i] = answer[i][rp] = 1;
}
}
dsu d2(n); // with 2s. if multiple 1 repres are in same comp, then create cycle from them;
REP(i, n){
REP(j, i){
if(p[i][j] == 2)
d2.join(i, j);
}
}
vector<vector<int>> buckets(n);
REP(i, n){
if(d.find(i) == i){
buckets[d2.find(i)].pb(i);
}
}
REP(i, n){
if(buckets[i].size() > 2){
REP(j, buckets[i].size()){
int u = buckets[i][j];
int v = buckets[i][(j + 1) % buckets[i].size()];
answer[u][v] = answer[v][u] = 1;
}
}
}
// now some connectivity checks;
// d2 is final connectivity; d are 1 components
// if p[i][j] == 0; they cant be connected in any way
// if p[i][j] == 2, they can't be connected in d;
REP(i, n){
REP(j, i){
if(p[i][j] == 0 && d2.sameSet(i, j))
return 0;
if(p[i][j] == 2 && d.sameSet(i, j))
return 0;
}
}
build(answer);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
supertrees.cpp:5:19: note: in expansion of macro 'FOR'
5 | #define REP(i, n) FOR(i, 0, n, 1)
| ^~~
supertrees.cpp:71:13: note: in expansion of macro 'REP'
71 | REP(j, buckets[i].size()){
| ^~~
supertrees.cpp:15:18: warning: 'd.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
15 | p.resize(n, -1);
| ^
supertrees.cpp:15:18: warning: 'd2.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
15 | p.resize(n, -1);
| ^
supertrees.cpp:15:18: warning: 'd2.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | 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... |