/*
* Created at 4:30 PM on 26 Jun, 2021
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
using namespace std;
#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define error(x) cout << #x << " = " << (x) << '\n'
#define trav(a, x) for(auto& (a): (x))
#define UNIQUE(x) (x).resize(distance((x).begin(),unique(ALL(x))))
#define DO if(true)
//typedef long long ll;
//typedef vector<ll> vi;
//typedef pair<ll,ll> pi;
#define mp make_pair
#define pb push_back
#define eb emplace_back
//#define int ll
typedef vector<int> vi;
typedef pair<int, int> pi;
//INF value
#ifndef int
#define INF int(2e9) + 15
#else
#define INF int(1e18) + 15
#endif
//All four are primes
#define mod 1000000007
#define hash_mod 23333333377
#define MT 1004006003999
#define hash_mod2 911382323
void setIO(const string &name = "") {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (name.length()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
template<typename T>
void read(vector<T> &a) {
for (auto &x: a) cin >> x;
}
template<typename T>
void read(vector<T> &a, int n) {
a.resize(n);
for (auto &x: a) cin >> x;
}
template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
out << "(";
out << v.first << "," << v.second;
return out << ")";
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
out << "[";
list(i, SZ(v)) {
if (i) out << ", ";
out << v[i];
}
return out << "]";
}
template<typename T>
void print(vector<T> &a) {
for (const auto &x: a) cout << x << ' ';
cout << '\n';
}
void MOD(int &x, int m = mod) {
x %= m;
if (x < 0) x += m;
}
void MOD(int64_t &x, int m = mod) {
x %= m;
if (x < 0) x += m;
}
#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)
template<typename T>
void dbg(const char *name, T &&arg1) {
cout << name << " : " << arg1 << '\n';
}
template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << " : " << arg1 << " | ";
dbg(comma + 1, args...);
}
template<class T>
void read(T &x) {
cin >> x;
}
template<class T, class... U>
void read(T &t, U &... u) {
read(t);
read(u...);
}
int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }
void build(vt<vi> b);
//void build(vt<vi> b){cout << b << '\n';}
struct DSU {
int size = 1;
vi link, sz;
explicit DSU(int n){
size = n;
link.resize(n);
iota(ALL(link), 0);
sz.assign(n, 1);
}
int find(int x){
while (x != link[x]){
x = link[x];
}
return x;
}
int same(int x, int y){
return find(x) == find(y);
}
void unite(int x, int y){
x = find(x), y = find(y);
if(x == y){
return;
}
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
link[y] = x;
}
};
using ll = int64_t;
#define N 1010
int n;
vt<vi> p;
int construct(vt<vi> P){
DO {
p = P;
n = SZ(p);
}
DSU dsu(n);
list(i, n){
rep(j, i + 1, n){
if(p[i][j]){
dsu.unite(i, j);
}
}
}
vt<vi> comp(n);
list(i, n){
comp[dsu.find(i)].eb(i);
}
vt<vi> ans(n, vi(n, 0));
vi way(n, 1);
int x, y;
list(i, n){
if(SZ(comp[i]) <= 1) continue;
rep(j, 1, SZ(comp[i])){
x = comp[i][j];
y = comp[i][j - 1];
ans[x][y] = 1;
ans[y][x] = 1;
}
x = comp[i].front(), y = comp[i].back();
if(p[x][y] == 2){
way[i] = 2;
ans[x][y] = 1;
ans[y][x] = 1;
}
}
bool possible = true;
list(i, n){
if(SZ(comp[i]) <= 1) continue;
possible &= (SZ(comp[i]) > 2);
list(j, SZ(comp[i])){
rep(k, j + 1, SZ(comp[i])){
possible &= (p[comp[i][j]][comp[i][k]] == way[i]);
}
}
}
if(!possible){
return 0;
}
build(ans);
return 1;
}
//int main(){
// cout << construct(vt<vi>{vi{1, 0}, vi{0, 1}}) << '\n';
//}
Compilation message
supertrees.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:90:5: note: in expansion of macro 'list'
90 | list(i, SZ(v)) {
| ^~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:195:5: note: in expansion of macro 'list'
195 | list(i, n){
| ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
supertrees.cpp:196:9: note: in expansion of macro 'rep'
196 | rep(j, i + 1, n){
| ^~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:204:5: note: in expansion of macro 'list'
204 | list(i, n){
| ^~~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:212:5: note: in expansion of macro 'list'
212 | list(i, n){
| ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
supertrees.cpp:215:9: note: in expansion of macro 'rep'
215 | rep(j, 1, SZ(comp[i])){
| ^~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:232:5: note: in expansion of macro 'list'
232 | list(i, n){
| ^~~~
supertrees.cpp:23:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
| ^
supertrees.cpp:236:9: note: in expansion of macro 'list'
236 | list(j, SZ(comp[i])){
| ^~~~
supertrees.cpp:22:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
| ^
supertrees.cpp:237:13: note: in expansion of macro 'rep'
237 | rep(k, j + 1, SZ(comp[i])){
| ^~~
supertrees.cpp: In function 'void setIO(const string&)':
supertrees.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
| 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 |
Answer gives possible 0 while actual possible 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1340 KB |
Output is correct |
| 9 |
Correct |
251 ms |
25996 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1340 KB |
Output is correct |
| 13 |
Correct |
246 ms |
25984 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
5 ms |
844 KB |
Output is correct |
| 17 |
Correct |
116 ms |
16068 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
71 ms |
6740 KB |
Output is correct |
| 22 |
Correct |
236 ms |
25984 KB |
Output is correct |
| 23 |
Correct |
226 ms |
25924 KB |
Output is correct |
| 24 |
Correct |
246 ms |
25948 KB |
Output is correct |
| 25 |
Correct |
109 ms |
16120 KB |
Output is correct |
| 26 |
Correct |
107 ms |
16068 KB |
Output is correct |
| 27 |
Correct |
246 ms |
25992 KB |
Output is correct |
| 28 |
Correct |
245 ms |
25924 KB |
Output is correct |
| 29 |
Correct |
102 ms |
16124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
57 ms |
7152 KB |
Output is correct |
| 5 |
Correct |
236 ms |
27888 KB |
Output is correct |
| 6 |
Incorrect |
106 ms |
17988 KB |
Answer gives possible 0 while actual possible 1 |
| 7 |
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 |
Answer gives possible 0 while actual possible 1 |
| 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 |
Answer gives possible 0 while actual possible 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
