#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,N) for(long long i = 0; (i) < (N); (i)++)
#define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++)
#define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc))
#define NL '\n'
#define EL cout << NL
#define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL
#define PRINTVV(v) for(auto a:(v)) {PRINTV(a);}
typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VLL;
typedef pair<ll,ll> PL;
typedef vector<PL> VPL;
typedef vector<VPL> VVPL;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector<bool> visited(n,0);
FOR(s,n) {
if (!visited[s]) {
vector<int> branch;
vector<int> cycle;
vector<int> comp;
vector<bool> incycle(n,false);
vector<int> adress(n,-1);
stack<pair<int,int>> st;
int bnum = 0;
st.push({s,0});
while(!st.empty()) {
int u = st.top().first;
int t = st.top().second;
st.pop();
if (visited[u]) continue;
//cout << u << " " << t << NL;
visited[u] = true;
bool is_cycle = true;
FOR(v,n) {
if (v == u) continue;
if (p[u][v] >= 1) {
is_cycle = is_cycle && (p[u][v] == 2);
int type = 0;
if (p[u][v] == 1) {
if (adress[v] > 0 && adress[v] < t) type = t = adress[v];
if (t > 0) type = t;
else if (adress[v] > 0) type = t = adress[v];
else t = type = ++bnum;
}
st.push({v,type});
}
}
if (is_cycle) {
cycle.push_back(u);
incycle[u] = true;
}
else branch.push_back(u);
adress[u] = t;
comp.push_back(u);
}
//PRINTV(branch);
//PRINTV(cycle);
//PRINTV(adress);
//PRINTV(incycle);
for (auto u: comp) {
for (auto v: comp) {
int expected = 2;
if ((adress[u] == adress[v]) && (adress[u] != 0)) expected = 1;
if (expected != p[u][v]) return 0;
}
}
for (auto u: branch) {
FOR(v,n) {
if (p[u][v] == 2 && !incycle[v]) {
return 0;
}
}
}
int prev_u = -1;
for(auto u: branch) {
if (prev_u >= 0) {
answer[u][prev_u] = answer[prev_u][u] = 1;
}
prev_u = u;
}
int prev_v = prev_u;
int first_c = prev_u;
for (auto v: cycle) {
if (prev_v >= 0) answer[v][prev_v] = answer[prev_v][v] = 1;
prev_v = v;
if (first_c == -1) first_c = v;
}
if (prev_v != first_c) answer[first_c][prev_v] = answer[prev_v][first_c] = 1;
}
}
build(answer);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 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 |
212 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 |
212 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 |
212 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 |
212 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 |
212 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
