| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 917582 | 2024-01-28T12:35:16 Z | alexdd | 항공 노선도 (JOI18_airline) | C++17 | 0 ms | 0 KB |
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> con[1100];
map<pair<int,int>,int> mp;
map<pair<int,int>,int> init;
int p,q;
int sum[1100];
void Bob(int V, int U, int C[], int D[])
{
for(int i=0;i<U;i++)
{
con[C[i]].push_back(D[i]);
con[D[i]].push_back(C[i]);
mp[{C[i],D[i]}]++;
mp[{D[i],C[i]}]++;
}
for(int i=0;i<V;i++)
{
if((int)con[i].size() == V-2)
{
p=i;
for(int j=0;j<V;j++)
if(j!=i && mp[{i,j}]==0)
q=j;
break;
}
}
vector<int> b(10);
b[0]=-1;
for(auto x:con[q])
{
int aux=0;
for(auto y:con[q])
if(mp[{x,y}])
aux++;
if(aux==1 && b[0]==-1)
b[0]=x;
else if(aux==1)
b[9]=x;
}
if((int)con[b[0]].size() < (int)con[b[9]].size())
swap(b[0],b[9]);
for(int i=1;i<9;i++)
{
for(auto x:con[q])
{
if((i==1 || x!=b[i-2]) && mp[{x,b[i-1]}])
{
b[i]=x;
break;
}
}
}
for(int i=0;i<10;i++)
for(auto x:con[b[i]])
sum[x] += (1<<i);
vector<pair<int,int>> rez;
for(int i=0;i<V;i++)
{
if(i!=p && i!=q && !mp[{q,i}])
{
//cout<<i<<" "<<sum[i]<<" sum\n";
for(auto x:con[i])
{
if(x!=p && x!=q && !mp[{q,x}] && init[{sum[x],sum[i]}]==0)
{
init[{sum[i],sum[x]}]++;
rez.push_back({sum[i],sum[x]});
}
}
}
}
InitMap(V-12,rez.size());
for(auto e:rez)
MakeMap(e.first,e.second);
}