# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
265498 | doowey | Airline Route Map (JOI18_airline) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "Boblib.h"
#include <cassert>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = 1050;
vector<int> T[N];
bool hh[N];
bool gg[N];
bool vis[N];
int deg[N];
int idx[N];
bool out[N];
void Bob( int V, int U, int C[], int D[] ){
int n = V - 13;
int m = U;
for(int i = 0 ; i < m; i ++ ){
T[C[i]].push_back(D[i]);
T[D[i]].push_back(C[i]);
}
int vso = -1;
for(int i = 0 ; i < V; i ++ ){
if(T[i].size() == n + 11){
vso = i;
hh[i]=true;
for(auto x : T[i]){
hh[x]=true;
}
break;
}
}
int al = -1;
for(int i = 0 ; i < V; i ++ ){
if(!hh[i]){
al = i;
}
}
gg[vso]=true;
for(auto x : T[al]){
gg[x]=true;
}
vector<int> bits;
for(int i = 0; i < V; i ++ ){
if(!gg[i]){
bits.push_back(i);
}
}
for(auto x : bits){
for(auto y : T[x]){
if(!gg[y]){
deg[x] ++ ;
}
else{
out[x]=true;
}
}
}
vector<int> ord;
int start = -1;
for(auto x : bits){
if(deg[x] == 1){
start = x;
}
}
bool went;
for(int i = 0 ; i < bits.size(); i ++ ){
vis[start] = true;
ord.push_back(start);
if(i + 1 == bits.size()) break;
went = false;
for(auto x : T[start]){
if(gg[x] || vis[x]) continue;
if(deg[x] == 2 || out[x]){
start = x;
went = true;
break;
}
}
if(!went){
for(auto x : T[start]){
if(gg[x] || vis[x] ) continue;
start = x;
break;
}
}
}
gg[vso] = false;
for(int i = 0 ; i < ord.size(); i ++ ){
for(auto x : T[ord[i]]){
if(gg[x]){
idx[x] += (1 << i);
}
}
}
vector<pii> sol;
for(int i = 0 ; i < V; i ++ ){
if(!gg[i]) continue;
for(auto x : T[i]){
if(!gg[x]) continue;
if(idx[i] < idx[x])
sol.push_back(mp(idx[i], idx[x]));
}
}
InitMap(n, sol.size());
for(auto x : sol)
MakeMap(x.fi, x.se);
}