| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 988163 | vjudge1 | Airline Route Map (JOI18_airline) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define CTD(D,I) for(auto i:adj[z]) {if(IN[i]&&i-w&&DEG[i]==D&&i!=v[I]){w=z,v.push_back(z=i);break;}}
vector<int>adj[1012];
int means[1024],val[1012],DEG[1012],IN[1012];
void Bob( int V, int U, int C[], int D[] ){
int CC=0;
for(int i=3;i<1024;i++)
if(__builtin_popcount(i)>1)
means[i]=CC++;
for(int i=0;i<U;i++)
adj[C[i]].push_back(D[i]),
adj[D[i]].push_back(C[i]);
int x,y,z,w=-1;
for(int i=0;i<V;i++)
if(adj[i].size()<2)
x=i;
y=adj[x][0];
for(auto j:adj[y])
IN[j]=1;
for(int i=0;i<V;i++)
for(auto j:adj[i])
DEG[i]+=IN[j];
for(auto i:adj[y])
if(DEG[i]==1)
z=i;
vector<int>v{z};
for(int Q=5;Q--;)for(auto i:adj[z])
if(IN[i]&&i-w){w=z,v.push_back(z=i);break;}
if(v.size()!=6) MakeMap(0,0);
for(auto i:adj[z]) CTD(4,0)
if(v.size()!=7) MakeMap(0,0);
for(auto i:adj[z]){
if(IN[i]&&i-w&&DEG[i]==3&&count(adj[i].begin(),adj[i].end(),v[5])){
w=z,v.push_back(z=i);break;}}
if(v.size()!=8) MakeMap(0,0);
for(auto i:adj[z]) CTD(3,5)
if(v.size()!=9) MakeMap(0,0);
for(auto i:adj[z]) CTD(2,0)
if(v.size()!=10) MakeMap(0,0);
for(int i=0;i<10;i++)
for(auto j:adj[v[i]])
val[j]+=1<<i;
vector<pair<int,int>>EEE;
for(int i=0;i<U;i++) if(!IN[C[i]]&&!IN[D[i]]) {
int A=means[val[C[i]]],B=means[val[D[i]]];
EEE.push_back({A,B});
}
swap(EEE.back(),EEE[0]);
InitMap(V-12,EEE.size());
for(auto[i,j]:EEE)
MakeMap(i,j);
}