| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 622871 | 2022-08-04T17:23:41 Z | CSQ31 | 항공 노선도 (JOI18_airline) | C++17 | 0 ms | 0 KB |
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define pb push_back
void Alice( int n, int m, int A[], int B[] ){
vector<array<int,2>>edge;
for(int i=0;i<m;i++){
edge.push_back({A[i],B[i]});
}
for(int i=0;i<n;i++){
for(int j=0;j<10;j++){
if(i&(1<<j)){
edge.push_back({i,j+n});
}
}
}
for(int j=0;j+1<10;j++)edge.push_back({j+n,j+n+1});
for(int j=0;j<10;j++){
edge.push_back({n+10,j+n});
edge.push_back({n+11,j+n});
}
InitG(n+12,sz(edge));
//cout<<vert<<" "<<M<<'\n';
int pos = 0;
for(auto x:edge)MakeG(pos++,x[0],x[1]);
}
bool vis[222222],mark[22222];
int lab[22222];
void Bob( int V, int U, int C[], int D[]){
//for(int i=0;i<U;i++)cout<<C[i]<<" "<<D[i]<<'\n';
vector<vector<int>>adj(V);
for(int i=0;i<U;i++){
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
}
for(int i=0;i<V;i++){
sort(adj[i].begin(),adj[i].end());
}
int n0 = 0,n1 = 0;
for(int i=0;i<V;i++){
for(int j=i+1;j<V;j++){
if(sz(adj[i]) != 10 || sz(adj[j])!=10)continue;
if(adj[i] == adj[j]){
n0 = i;
n1 = j;
break;
}
}
} //the ten bits
//cout<<"TES"<<'\n';
//cout<<n0<<" "<<n1<<'\n';
vector<int>bit;
for(int x:adj[n0]){
bit.pb(x);
mark[x] = 1;
}
int root = 0;
for(int i=0;i<10;i++){ //find a enpoint
int deg = 0;
for(int x:adj[bit[i]])deg+=mark[x];
if(deg==1)root = bit[i];
}
queue<int>q;
q.push(root);
vis[root] = 1;
vector<int>ord;
while(!q.empty()){
int v = q.front();
ord.pb(v);
q.pop();
for(int x:adj[v]){
if(!vis[x] && mark[x]){
vis[x] = 1;
q.push(x);
}
}
}
//for(int x:ord)cout<<x<<" ";
//cout<<'\n';
if(sz(adj[ord[0]]) < sz(adj[ord[9]]))reverse(ord.begin(),ord.end());
//wrong order
for(int i=0;i<V;i++){
if(mark[i] || i==n0 || i==n1)continue;
for(int x:adj[i]){
if(mark[x]){
for(int j=0;j<10;j++){
if(ord[j] ==x)lab[i]+=(1<<j);
}
}
}
}
vector<array<int,2>>edge;
for(int i=0;i<V;i++){
if(mark[i] || i==n0 || i==n1)continue;
for(int x:adj[i]){
if(mark[x] || x==n0 || x==n1)continue;
if(x > i)edge.pb({lab[i],lab[x]});
}
}
InitMap(V-12,sz(edge));
for(auto x:edge){
//MakeMap(x[0],x[1]);
//cout<<x[0]<<" "<<x[1]<<'\n';
}
for(auto x:edge){
MakeMap(x[0],x[1]);
//cout<<x[0]<<" "<<x[1]<<'\n';
}
}