#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
#include "supertrees.h"
using namespace std;
// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;
int find(vector<int>& p, int x) {
return p[x] == x ? x : (p[x] = find(p, p[x]));
}
void merge(vector<int>& p, int x, int y) {
p[find(p, x)] = find(p, y);
}
int construct(vector<vector<int>> p) {
int n = sz(p);
vector<vector<int>> ret;
for(int i = 0; i < n; i++) {
vector<int> t(n);
ret.pb(t);
}
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 3) return 0;
vector<int> connectedcomponent(n);
iota(all(connectedcomponent), 0);
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j]) merge(connectedcomponent, i, j);
// check zero
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 0 && find(connectedcomponent, i) == find(connectedcomponent, j)) return 0;
// check one
vector<int> oneedge(n);
iota(all(oneedge), 0);
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 1) merge(oneedge, i, j);
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] != 1 && find(oneedge, i) != find(oneedge, j)) return 0;
map<int, int> treetoroot;
for(int i = 0; i < n; i++) {
if(!treetoroot.count(find(oneedge, i))) {
treetoroot[find(oneedge, i)] = i;
}
else {
ret[find(oneedge, i)][i] = 1;
ret[i][find(oneedge, i)] = 1;
}
}
map<int, set<int>> roots;
for(int i = 0; i < n; i++) {
roots[find(connectedcomponent, i)].insert(treetoroot[find(oneedge, i)]);
}
for(auto out: roots) {
if(sz(out.s) == 2) return 0;
if(sz(out.s) == 1) continue;
vector<int> v(all(out.s));
for(int i = 0; i < sz(v); i++) {
int j = (i+1)%sz(v);
ret[v[i]][v[j]] = 1;
ret[v[j]][v[i]] = 1;
}
}
build(ret);
return 1;
}
/*
void solve() {
}
// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
b[1][1] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
b[1][1] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
b[1][1] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
b[1][1] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
