# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1216505 | LeonidCuk | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<bool>vis;
void dfs(int i,vector<vector<int>>&p,vector<vector<int>>&res)
{
int n=p.size();
vis[j]=true;
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(p[i][j]==1&&vis[j]==0)
{
res[i][j]=1;
dfs(j,p,res);
}
}
vector<int>ok;
ok.push_back(i);
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(p[i][j]==2&&vis[j]==0)
{
res[i][j]=1;
vis[j]=1;
ok.push_back(j);
}
}
ok.push_back(i);
if(ok.size()==2)return;
for(int j=1;j<ok.size();j++)
{
res[ok[j]][ok[j-1]]=1;
}
}
int construct(vector<vector<int>> p)
{
int n=p.size();
vis.resize(n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(p[i][j]==3)return 0;
}
}
vector<vector<int>>res(n,vector<int>(0));
for(int i=0;i<n;i++)
{
if(vis[i]==0)dfs(i,p,res);
}
build(res);
return 1;
}