#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
using namespace std;
const int MAXN = 1e3+10;
const double SMALL = 1e-6;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int n;
bool tag[MAXN], done[MAXN];
vector <vector<int>> adj;
vector <int> cc[MAXN];
void bd(int x, int y){
adj[x][y] = 1; adj[y][x] = 1;
}
struct DSU {
int par[MAXN], siz[MAXN];
void bd(){
for(int i=0; i<n; i++){
par[i] = i; siz[i] = 1;
cc[i].pb(i);
}
}
int f(int x){
if(x == par[x]) return x;
return par[x] = f(par[x]);
}
bool con(int x, int y){
return f(x) == f(y);
}
void mer(int x, int y){
if(con(x, y)) return;
x = f(x); y = f(y);
if(siz[x] > siz[y]) swap(x, y);
par[x] = y; siz[y] += siz[x];
for(auto in : cc[x]) cc[y].pb(in);
}
} A;
int construct(vector<vector<int>> p) {
n = p.size();
vector <int> te(n);
for(int i=0; i<n; i++) adj.pb(te);
A.bd();
for(int i = 0; i < n; i++) {
if(done[i]) continue;
for(int x=0; x<n; x++) tag[x] = 0;
vector <int> vec; vec.pb(i); tag[i] = 1;
for(int j=i+1; j < n; j++){
if(p[i][j] == 1){
vec.pb(j); tag[j] = 1;
}
}
//for(auto in : vec) cout << in << "pp\n";
for(auto in : vec){
//cout << in << " in\n";
done[in] = 1;
for(int x=0; x<n; x++){
if(tag[x] && p[in][x] != 1) return 0; //harusnya 1
if(!tag[x] && p[in][x] == 1) return 0;
}
}
for(int i=0; i+1<vec.size(); i++){ // build
bd(vec[i], vec[i+1]);
A.mer(vec[i], vec[i+1]);
}
}
// for(int i=0; i<n; i++){
// for(int j=0; j<n; j++) cout << adj[i][j] << ' ';
// cout << '\n';
// }
for(int i=0; i<n; i++) done[i] = 0;
for(int i = 0; i < n; i++) {
if(done[i]) continue;
for(int x=0; x<n; x++) tag[x] = 0;
vector <int> vec; vec.pb(i); tag[i] = 1;
for(int j=i+1; j < n; j++){
if(p[i][j] == 2){
vec.pb(j); tag[j] = 1;
}
}
if(vec.size() <= 2) return 0;
for(auto x : vec){
for(auto y : vec){
if(x==y) continue;
if(A.con(x, y)) return 0;
}
}
//for(auto in : vec) cout << in << "pp\n";
for(auto in : vec){
//cout << in << " in\n";
done[in] = 1;
for(int x=0; x<n; x++){
if(x==in) continue;
if(tag[x] && p[in][x] != 2) return 0; //harusnya 1
if(!tag[x] && p[in][x] == 2) return 0;
}
}
for(int i=0; i+1<vec.size(); i++){ // build
bd(vec[i], vec[i+1]);
}
bd(vec[0], vec.back());
}
for(int i=0; i<n; i++) adj[i][i] = 0;
build(adj);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0; i+1<vec.size(); i++){ // build
| ~~~^~~~~~~~~~~
supertrees.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i=0; i+1<vec.size(); i++){ // build
| ~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
