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 <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int d[1005], T;
vector<vector<int> > b;
vector<int> c[2005], v[2005], e[2005];
bool tt[2005], tl[2005];
struct dsu
{
ll d[2005];
void make_sets(int h)
{
for (int i = 0; i < h; i++) d[i]=i;
}
ll find_set(int h)
{
if (h==d[h]) return h; else return d[h]=find_set(d[h]);
}
void unite_sets(int x,int y)
{
x=find_set(x);
y=find_set(y);
d[x]=y;
}
} g, gg;
void dfs(int h)
{
tt[h]=1;
d[h]++;
for (int i = 0; i < c[h].size(); i++)
if (!tt[c[h][i]])
{
dfs(c[h][i]);
}
tt[h]=0;
}
int construct(vector<vector<int> > a)
{
ll n=a.size();
b.resize(n);
for (int i = 0; i < n; i++)
b[i].resize(n, 0);
g.make_sets(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j]==1)
g.unite_sets(i, j);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j]!=1 && g.find_set(i)==g.find_set(j))
{
return 0;
}
vector<ll> z;
for (int i = 0; i < n; i++)
{
if (g.find_set(i)==i)
{
z.pb(i);
}
v[g.find_set(i)].pb(i);
}
for (int i = 0; i < z.size(); i++)
{
for (int u = 0; u < v[z[i]].size()-1; u++)
{
b[v[z[i]][u+1]][v[z[i]][u]]=1;
b[v[z[i]][u]][v[z[i]][u+1]]=1;
c[v[z[i]][u+1]].pb(v[z[i]][u]);
c[v[z[i]][u]].pb(v[z[i]][u+1]);
}
}
gg.make_sets(n);
for (int i = 0; i < z.size(); i++)
for (int j = 0; j < z.size(); j++)
{
ll p=-1;
for (int u = 0; u < v[z[i]].size(); u++)
for (int q = 0; q < v[z[j]].size(); q++)
if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else
if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0;
if (p==2)
gg.unite_sets(z[i], z[j]);
}
for (int i = 0; i < z.size(); i++)
for (int j = 0; j < z.size(); j++)
{
ll p=-1;
for (int u = 0; u < v[z[i]].size(); u++)
for (int q = 0; q < v[z[j]].size(); q++)
if (p==-1) p=a[v[z[i]][u]][v[z[j]][q]]; else
if (p!=a[v[z[i]][u]][v[z[j]][q]]) return 0;
if (p==0 && gg.find_set(z[i])==gg.find_set(z[j]))
return 0;
}
for (int i = 0; i < z.size(); i++)
e[gg.find_set(z[i])].pb(z[i]);
for (int i = 0; i < z.size(); i++)
if (gg.find_set(z[i])==z[i])
{
if (e[z[i]].size()<3)
{
return 0;
}
for (int j = 0; j < e[z[i]].size(); j++)
{
ll u=(j+1)%((int)e[z[i]].size());
b[e[z[i]][j]][e[z[i]][u]]=1;
b[e[z[i]][u]][e[z[i]][j]]=1;
c[e[z[i]][j]].pb(e[z[i]][u]);
c[e[z[i]][u]].pb(e[z[i]][j]);
}
}
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
}*/
build(b);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < c[h].size(); i++)
| ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < z.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int u = 0; u < v[z[i]].size()-1; u++)
| ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < z.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int j = 0; j < z.size(); j++)
| ~~^~~~~~~~~~
supertrees.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int u = 0; u < v[z[i]].size(); u++)
| ~~^~~~~~~~~~~~~~~~
supertrees.cpp:100:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int q = 0; q < v[z[j]].size(); q++)
| ~~^~~~~~~~~~~~~~~~
supertrees.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int i = 0; i < z.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int j = 0; j < z.size(); j++)
| ~~^~~~~~~~~~
supertrees.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int u = 0; u < v[z[i]].size(); u++)
| ~~^~~~~~~~~~~~~~~~
supertrees.cpp:112:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int q = 0; q < v[z[j]].size(); q++)
| ~~^~~~~~~~~~~~~~~~
supertrees.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < z.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < z.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int j = 0; j < e[z[i]].size(); j++)
| ~~^~~~~~~~~~~~~~~~
# | 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... |