| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 313586 | mohamedsobhi777 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
std::vector<std::vector<int>> answer, p, pp ;
map<int, int> vis;
bool bad;
int nn;
vector<int> vecs(int x)
{
vector<int> ret;
queue<int> qu;
qu.push(x);
while (qu.size())
{
int x = qu.front();
qu.pop();
if (vis[x]++)
continue;
ret.push_back(x);
for (int i = 0; i < nn; ++i)
{
if (i == x || vis[i] || !p[x][i])
continue;
qu.push(i);
}
}
return ret;
}
void solve(vector<int> vecs)
{
map<int, int> viz;
if (vecs.size() < 2)
{
return;
}
else if (vecs.size() == 2)
{
if (p[vecs[0]][vecs[1]] != 1)
bad = 1;
answer[vecs[0]][vecs[1]] = answer[vecs[1]][vecs[0]] = 1;
return;
}
vector<vector<int>> lines;
int sz = (int)vecs.size();
for (int i = 0; i < sz; ++i)
{
int v = vecs[i];
if (viz[v]++)
continue;
lines.push_back({v});
for (int j = 0; j < sz; ++j)
{
if (i == j || viz[vecs[j]])
{
continue;
}
if (p[v][vecs[j]] == 1)
{
viz[vecs[j]] = 1;
lines.back().push_back(vecs[j]);
}
}
}
if (lines.size() == 2)
{
bad = 1;
}
for (int i = 0; i < (int)lines.size(); ++i)
{
int j = (i + 1) % (int)lines.size();
int x = lines[i][0], y = lines[j][0];
if (x != y)
answer[vecs[x]][vecs[y]] = answer[vecs[y]][vecs[x]] = 1;
for (int k = 1; k < (int)lines[i].size(); ++k)
{
int x = lines[i][k - 1], y = lines[i][k];
answer[vecs[x]][vecs[y]] = 1;
answer[vecs[y]][vecs[x]] = 1;
}
}
}
void clear()
{
p.clear();
answer.clear();
vis.clear();
bad = 0;
}
int vix[1001];
int root;
void dfs(int x)
{
vix[x] = 1;
if (x != root)
p[root][x]--;
for (int j = 0; j < n; ++j)
{
if (x != j && pp[x][j] && !vix[j])
{
dfs(j) ;
}
}
vis[x] = 0;
}
bool check()
{
pp = p ;
for (int i = 0; i < n; ++i)
{
memset(vix, 0, sizeof vix);
root = i;
dfs(i);
}
for(int i = 0 ;i < n; ++ i){
for(int j = 0 ;j < n; ++ j){
//cout<< p[i][j] <<" " ;
if(i == j)continue ;
if(p[i][j])return 0 ;
}
//cout<<"...\n" ;
}
return 1;
}
int construct(std::vector<std::vector<int>> P)
{
clear();
p = P;
nn = p.size();
for (int i = 0; i < nn; i++)
{
std::vector<int> row;
row.resize(nn);
answer.push_back(row);
}
for (int i = 0; i < nn; ++i)
{
vector<int> g = vecs(i);
solve(g);
}
if (bad)
return 0;
if (!check())
return 0;
build(answer);
return 1;
}