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 "grader.cpp"
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
struct DSU{
vi parent, size;
void init(int n){
parent.resize(n);
size.resize(n, 1);
iota(parent.begin(), parent.end(), 0);
}
int get_size(int v){
return size[v];
}
int find_parent(int v){
if(parent[v] == v) return v;
return parent[v] = find_parent(parent[v]);
}
void merge(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a != b){
if(size[b] > size[a]) swap(a,b);
parent[b] = a;
size[a] += size[b];
}
}
};
vi G[1001], G2[1001];
int construct(vector<vi> p){
int n = p.size();
vector<vi> answer(n, vi(n, 0));
DSU dsu, dsu2;
dsu.init(n);
dsu2.init(n);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(p[i][j] == 1) dsu.merge(i, j);
if(p[i][j] == 3) return 0;
}
}
for(int i = 0; i < n; i++){
G[dsu.find_parent(i)].pb(i);
}
for(int i = 0; i < n; i++){
if(G[i].size() ==0) continue;
for(int j = 0; j < (int)G[i].size(); j++){
for(int k = j+1; k < (int)G[i].size(); k++){
if(p[G[i][k]][G[i][j]] != 1) return 0;
}
}
for(int j = 0; j < (int)G[i].size()-1; j++){
answer[G[i][j]][G[i][j+1]] = 1;
answer[G[i][j+1]][G[i][j]] = 1;
}
}
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(p[i][j] == 2)
dsu2.merge(dsu.find_parent(i), dsu.find_parent(j));
}
}
for(int i = 0; i < n; i++){
if(G[i].size()==0) continue;
G2[dsu2.find_parent(i)].pb(i);
}
for(int i = 0; i < n; i++){
if(G2[i].size() < 2) continue;
if(G2[i].size() == 2) return 0;
for(int j = 0; j < (int)G2[i].size(); j++){
for(int k = j + 1; k < (int)G2[i].size(); k++){
for(auto t : G[G2[i][j]]){
for(auto s : G[G2[i][k]]){
if(p[t][s] != 2) return 0;
}
}
}
}
for(int j = 0; j < (int)G2[i].size()-1; j++){
answer[G2[i][j]][G2[i][j+1]] = 1;
answer[G2[i][j+1]][G2[i][j]] = 1;
}
answer[G2[i].back()][G2[i][0]] = 1;
answer[G2[i][0]][G2[i].back()] = 1;
}
build(answer);
return 1;
}
# | 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... |