| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 386014 | AdOjis485 | Connecting Supertrees (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int construct(vector<vector<int>> p)
{
int n = p.size();
map<vector<int>, int> m;
vector<vector<int> > parts;
vector<int> cyc;
for(int i = 0; i < n; i ++)
{
if(m.count(p[i]) == 0)
{
bool two = false;
bool even = true;
for(int j = 0; j < n; j ++)
{
if(p[i][j] == 1) even = false;
else if(p[i][j] == 2) two = true;
}
if(two && even)
{
cyc.push_back(i);
}
else
{
m[p[i]] = m.size();
parts.push_back({i});
}
}
else parts[m[p[i]]].push_back(i);
}
vector<bool> done(n);
vector<vector<int> > answer(n, vector<int> (n));
/*
cerr << "parts:\n";
for(auto part : parts)
{
for(auto el : part) cerr << el << " ";
cerr << '\n';
}
cerr << "cyc:\n";
for(auto el : cyc) cerr << el << " ";
cerr << '\n';
*/
bool poss = true;
for(int i = 0; i < n; i ++)
{
vector<int> comp;
if(done[i]) continue;
int last = -1;
int first = -1;
int compsizecount = 0;
int compsizei = 0;
for(int j = 0; j < n; j ++) compsizei += (p[i][j] > 0);
for(int j = 0; j < parts.size(); j ++)
{
if(p[i][parts[j][0]] == 0) continue;
if(first < 0) first = parts[j][0];
int compsizecur = 0;
for(int el : p[parts[j][0]]) compsizecur += (el > 0);
if(compsizecur != compsizei) poss = false;
for(int k = 0; k < parts[j].size(); k ++)
{
int cur = parts[j][k];
done[cur] = true;
comp.push_back(cur);
compsizecount ++;
if(k == 0)
{
if(last >= 0)
{
answer[cur][last] = 1;
answer[last][cur] = 1;
}
}
else
{
answer[cur][parts[j][k - 1]] = 1;
answer[parts[j][k - 1]][cur] = 1;
}
}
last = parts[j][0];
}
for(int el : cyc)
{
if(p[el][i] > 0)
{
done[el] = true;
compsizecount ++;
comp.push_back(el);
int compsizecur = 0;
for(int el2 : p[el]) compsizecur += (el2 > 0);
if(compsizecur != compsizei) poss = false;
if(first < 0) first = el;
if(last >= 0)
{
answer[el][last] = 1;
answer[last][el] = 1;
}
last = el;
}
}
if(last != first)
{
answer[first][last] = 1;
answer[last][first] = 1;
}
for(int a : comp)
{
for(int b : comp) if(p[a][b]] == 0) poss = false;
}
if(compsizecount != compsizei) poss = false;
}
for(auto part : parts)
{
int count = 0;
for(auto el : p[part[0]]) count += el % 2;
poss &= (count == part.size());
}
if(poss)
{
build(answer);
return 1;
}
else return 0;
}