#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
/*void build(vector<vector<int>>& ans){
for(int i = 0; i < (int)ans.size(); i++){
for(int j = 0; j < (int)ans.size(); j++)cout << ans[i][j] << ' ';
cout << '\n';
}
}*/
struct UFDS {
vector<int> p,siz;
void init(int n){
p.resize(n + 3);
siz.resize(n + 3);
for(int i = 0; i <= n; i++){
p[i] = i;
siz[i] = 1;
}
}
int get(int x){
return p[x]=(x==p[x] ? x : get(p[x]));
}
void unio(int u , int v){
int a = get(u);
int b=get(v);
if(a==b)return;
if(siz[a]>siz[b])swap(a,b);
p[b]=a;
siz[a]+=siz[b];
}
};
vector<vector<int>> b;
vector<int> adj[2003];
int help(vector<int>& v){
UFDS uf;
int n = v.size();
uf.init(n + 2);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n;j++){
if(b[v[i]][v[j]] == 1){
uf.unio(i,j);
}
}
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(uf.get(i) == uf.get(j) && b[v[i]][v[j]] == 2)return -1;
}
}
vector<vector<int>> v1;
bool vis1[n + 1];
memset(vis1,0,sizeof vis1);
for(int i = 0; i < n; i++){
if(!vis1[i]){
vector<int> x;
x.pb(v[i]);
vis1[i] = 1;
for(int j = i+1; j < n; j++){
if(uf.get(i) == uf.get(j)){
x.pb(v[j]);
vis1[j] = 1;
}
}
v1.pb(x);
}
}
for(int i = 0; i < (int)v1.size(); i++){
if(i == (int)v1.size()-1){
if(i!=0 && i!=1){
adj[v1[i][0]].pb(v1[0][0]);
adj[v1[0][0]].pb(v1[i][0]);
}
}
else {
adj[v1[i][0]].pb(v1[i + 1][0]);
adj[v1[i+1][0]].pb(v1[i][0]);
}
}
for(int i = 0; i < (int)v1.size(); i++){
for(int j = 1; j < (int)v1[i].size(); j++){
adj[v1[i][j]].pb(v1[i][j-1]);
adj[v1[i][j-1]].pb(v1[i][j]);
}
}
return 1;
}
int construct(std::vector<std::vector<int>> v){
int n = v.size();
UFDS d;
b = v;
d.init(n + 2);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(v[i][j]!=0)d.unio(i,j);
}
}
for(int i = 0; i < n; i++){
for(int j = i + 1 ;j < n; j++){
if(v[i][j] == 0 && d.get(i) == d.get(j))return -1;
}
}
vector<vector<int>> com;
bool vis[n + 1];
memset(vis,0,sizeof vis);
for(int i = 0; i < n; i++){
if(!vis[i]){
vector<int> x;
x.pb(i);
vis[i] = 1;
for(int j = i+1; j < n; j++){
if(d.get(i) == d.get(j)){
x.pb(j);
vis[j] = 1;
}
}
com.pb(x);
}
}
vector<vector<int>> ans(n,vector<int> (n,0));
for(int i = 0; i < (int)com.size(); i++){
int x = help(com[i]);
if(x == -1)return 0;
}
for(int i = 0; i < n; i++){
for(int j : adj[i]){
ans[i][j] = 1;
}
}
build(ans);
return 1;
}
/*
void solve(){
int n;
cin >> n;
vector<vector<int>> t(n,vector<int>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)cin >> t[i][j];
}
construct(t);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1356 KB |
Output is correct |
7 |
Correct |
197 ms |
26040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1356 KB |
Output is correct |
7 |
Correct |
197 ms |
26040 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
9 ms |
1392 KB |
Output is correct |
13 |
Correct |
181 ms |
26028 KB |
Output is correct |
14 |
Incorrect |
0 ms |
332 KB |
WA in grader: Invalid return value of construct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Incorrect |
1 ms |
332 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
45 ms |
6724 KB |
Output is correct |
5 |
Correct |
199 ms |
26024 KB |
Output is correct |
6 |
Correct |
217 ms |
26000 KB |
Output is correct |
7 |
Correct |
213 ms |
26024 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
54 ms |
6736 KB |
Output is correct |
10 |
Correct |
176 ms |
26040 KB |
Output is correct |
11 |
Correct |
189 ms |
26040 KB |
Output is correct |
12 |
Correct |
177 ms |
26044 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
45 ms |
6832 KB |
Output is correct |
17 |
Correct |
183 ms |
26076 KB |
Output is correct |
18 |
Correct |
192 ms |
26296 KB |
Output is correct |
19 |
Correct |
173 ms |
26040 KB |
Output is correct |
20 |
Correct |
175 ms |
26108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1356 KB |
Output is correct |
7 |
Correct |
197 ms |
26040 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
9 ms |
1392 KB |
Output is correct |
13 |
Correct |
181 ms |
26028 KB |
Output is correct |
14 |
Incorrect |
0 ms |
332 KB |
WA in grader: Invalid return value of construct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1356 KB |
Output is correct |
7 |
Correct |
197 ms |
26040 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
9 ms |
1392 KB |
Output is correct |
13 |
Correct |
181 ms |
26028 KB |
Output is correct |
14 |
Incorrect |
0 ms |
332 KB |
WA in grader: Invalid return value of construct |
15 |
Halted |
0 ms |
0 KB |
- |