This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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();
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;
}
}
}
build(answer);
return 1;
}
Compilation message (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:65:13: note: in expansion of macro 'REP'
65 | 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: 'd.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
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... |