| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1046546 | sofijavelkovska | 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 "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int> > adj)
{
int n=adj.size();
vector<vector<int> > answer;
for (int i=0; i<n; i++)
{
vector<int> row;
row.resize(n, 0);
answer.push_back(row);
}
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
if (adj[i][j]==3)
return 0;
int visited[n]={0};
queue<int> q;
vector<int> component;
vector<vector<int> > subcomponents;
for (int i=0; i<n; i++)
{
if (visited[i])
continue;
visited[i]=1;
q.push(i);
component.clear();
while (!q.empty())
{
int x=q.front();
q.pop();
component.push_back(x);
for (int j=0; j<n; j++)
if (adj[x][j]>0 && !visited[j])
{
visited[j]=1;
q.push(j);
}
}
subcomponents.clear();
while (!q.empty())
q.pop();
for (auto x : component)
{
if (visited[x]==2)
continue;
visited[x]=2;
q.push(x);
vector<int> newcomp;
subcomponents.push_back(newcomp);
while (!q.empty())
{
int y=q.front();
q.pop();
subcomponents.back().push_back(y);
for (auto z : component)
if (y!=z && adj[y][z]==1 && visited[z]!=2)
{
visited[z]=2;
q.push(z);
}
}
}
/*for (auto c : subcomponents)
{
cout << "subc ";
for (auto x : c)
cout << x << ' ';
cout << '\n';
}
cout << "end\n";*/
for (int j=0; j<subcomponents.size(); j++)
{
for (int t=0; t<subcomponents[j].size(); t++)
for (int k=t+1; k<subcomponents[j].size(); k++)
if (adj[subcomponents[j][t]][subcomponents[j][k]]!=1)
return 1;
for (auto x : subcomponents[j])
for (int t=0; t<subcomponents.size(); t++)
{
if (t==j)
continue;
for (auto y : subcomponents[t])
if (adj[x][y]!=2)
return 0;
}
}
for (int j=0; j<subcomponents.size(); j++)
for (int t=0; t<subcomponents[j].size()-1; t++)
{
int x=subcomponents[j][t];
int y=subcomponents[j][t+1];
answer[x][y]=1;
answer[y][x]=1;
}
if (subcomponents.size()==1)
continue;
if (subcomponents.size()==2)
{
int x=subcomponents[0][0];
int y=subcomponents[1][0];
answer[x][y]=1;
answer[y][x]=1;
}
for (int j=0; j<subcomponents.size(); j++)
{
int x=subcomponents[j][0];
int y=subcomponents[(j+1)%subcomponents.size()][0];
answer[x][y]=1;
answer[y][x]=1;
}
}
build(answer);
return 1;
}