| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1037565 | sleepntsheep | 수천개의 섬 (IOI22_islands) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "islands.h"
#include <variant>
#include <vector>
#include<set>
using namespace std;
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
vector<vector<int>> a(N);
for (int i = 0; i < M; ++i)
a[U[i]].push_back(i);
int is_sub2 = N<=400;
static int id[401][401];
if(N<=400){
memset(id, -1, sizeof id);
for(int i=0;i<M;++i)id[U[i]][V[i]]=i;
for(int i=0;i<N;++i)for(int j=i+1;j<N;++j)
if(id[i][j]==-1 ||id[j][i]==-1)is_sub2=0;
}
if (N==2){
if(a[0].size()>=2&&a[1].size()){
int a1=a[0][0],a2=a[0][1],a3=a[1][0];
return vector<int>{a1, a3, a2, a1, a3, a2};
}
return false;
}else if(is_sub2){
int a1=id[0][1],a2=id[1][0],a3=id[1][2],a4=id[2][1],a5=id[2][0],a6=id[0][2];
return vector<int>{a1,a3,a5,a6,a4,a2,a5,a3,a1,a2,a4,a6};
}else{
set<pair<int,int>>w;
for(int i=0;i<M;++i)w.emplace(U[i],V[i]);
for(int i=1;i<N;++i)for(int j=i+1;j<N;++j){
if(w.count({0,i})+w.count({i,j})+w.count({j,0})==3){
int a1=id[0][i],a2=id[i][0],a3=id[i][j],a4=id[j][i],a5=id[j][0],a6=id[0][j];
return vector<int>{a1,a3,a5,a6,a4,a2,a5,a3,a1,a2,a4,a6};
}
return false;
}
}
}