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 <vector>
#include<bits/stdc++.h>
using namespace std ;
const int N = 1002;
int dsu[N] , sz[N];
int get(int u){
if(u == dsu[u])
return u ;
return dsu[u] = get(dsu[u]);
}
void connect(int u , int v){
u = get(u) , v = get(v);
if(u == v)return ;
if(sz[u] > sz[v])swap(u , v);
sz[v] += sz[u];
dsu[u] = v ;
}
bool same(int u , int v){
u = get(u) , v = get(v);
return u == v ;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer (n , vector<int> (n , 0));
for(int i = 0 ; i < n ; i ++)sz[i] = 1 , dsu[i] = i ;
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
if(p[i][j])connect(i , j);
}
}
map<int, set<int> > mp ;
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ;j ++)
{
if(p[i][j] == 0&& same(i , j) || (p[i][j] && sz[get(dsu[i])] == 2))return 0 ;
if(p[i][j] && i != j)mp[dsu[i]].insert(i) , mp[dsu[i]].insert(j);
}
}
for(auto f : mp){
int past = *(f.second.begin());
auto p = f.second .begin();
p ++ ;
for(int i = 1 ; i < f.second.size() ; i ++){
int curr = *p;
p ++;
answer[past][curr] = answer[curr][past] = 1 ;
past = curr ;
}
p -- ;
past = *f.second.begin();
answer[past][*p] = answer[*p][past] = 1 ;
}
build(answer);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:57:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
57 | if(p[i][j] == 0&& same(i , j) || (p[i][j] && sz[get(dsu[i])] == 2))return 0 ;
supertrees.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 1 ; i < f.second.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... |