| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 595295 | Red_Inside | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
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 "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int used[maxn], good[maxn];
int construct(vector <vector <int> > a)
{
int n = a[0].size();
vector <vector <int> > ans;
ans = a;
forn(0, i, n-1) forn(0, j, n-1) ans[i][j] = 0;
vector <int> roots;
forn(0, i, n-1)
{
if(a[i][i] != 1) return 0;
if(used[i]) continue;
vector <int> vec;
forn(0, j, n-1)
{
if(a[i][j] == 1)
{
vec.pb(j);
used[j] = 1;
}
}
FOR(0, j, vec.size())
{
forn(0, k, n-1)
{
if(a[i][k] == 1 && a[vec[j]][k] != 1) return 0;
if(a[i][k] != 1 && a[vec[j]][k] == 1) return 0;
}
}
FOR(1, j, vec.size())
{
ans[vec[j]][vec[j-1]] = 1;
ans[vec[j-1]][vec[j]] = 1;
}
// cout << "NEW TREE: ";
// for(auto j : vec) cout << j << " ";
// cout << endl;
for(auto j : vec) root[j] = vec[0];
roots.pb(vec[0]);
}
forn(0, i, n-1) used[i] = 0;
FOR(0, i, roots.size())
{
if(used[i]) continue;
vector <int> vec;
FOR(0, j, roots.size())
{
if(a[roots[i]][roots[j]] == 2)
{
used[j] = i + 1;
vec.pb(roots[j]);
}
}
vec.pb(roots[i]);
if(vec.size() == 2) return 0;
if(vec.size() == 1) continue;
FOR(0, j, vec.size())
{
FOR(j + 1, k, vec.size())
{
if(a[vec[j]][vec[k]] != 2) return 0;
}
}
FOR(0, j, vec.size())
{
forn(0, k, n-1)
{
if(!(a[vec[j]][k] == 2 && a[roots[i]][root[k]] == 2)) return 0;
if(!(a[vec[j]][k] == 0 && a[roots[i]][root[k]] == 0)) return 0;
}
}
FOR(1, j, vec.size())
{
ans[vec[j]][vec[j-1]] = 1;
ans[vec[j-1]][vec[j]] = 1;
}
ans[vec[0]][vec.back()] = 1;
ans[vec.back()][vec[0]] = 1;
}
build(ans);
return 1;
}