| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 328881 | blue | 슈퍼트리 잇기 (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 <vector>
#include <set>
int construct(vector< vector<int> > p)
{
int n = p.size();
vector< vector<int> > b(n);
for(int i = 0; i < n; i++) b[i] = vector<int>(n, 0);
vector<int> group(n, -1);
set<int> grouplist;
for(int i = 0; i < n; i++)
{
group[i] = i;
grouplist.clear();
for(int j = 0; j < i; j++) if(p[i][j]) grouplist.insert(group[j]);
for(int j = 0; j < i; j++) if(grouplist.find(group[j]) != grouplist.end()) group[j] = i;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(group[i] == group[j] && p[i][j] == 0) return 0;
if(group[i] != group[j] && p[i][j] == 1) return 0;
}
}
for(int i = 0; i < n; i++)
{
for(int j = i-1; j >= 0; j--)
{
if(p[i][j])
{
b[i][j] = b[j][i] = 1;
break;
}
}
}
for(int i = 0; i < n; i++)
{
int A, B;
for(A = 0; A < n; A++) if(group[A] == i) break;
if(A >= n) continue;
for(B = n-1; B > A; B--) if(group[B] == i) break;
if(B <= A) continue;
b[A][B] = b[B][A] = 1;
}
build(b);
return 1;
}