| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1280125 | enzy | 항공 노선도 (JOI18_airline) | C++20 | 0 ms | 0 KiB |
#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
void Alice( int n, int m, int A[], int B[] ){
int sb=0;
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
InitG(n+12,m+n+20+sb+9);
for(int i=0;i<m;i++) MakeG(A[i],B[i]);
for(int i=0;i<=n+10;i++) if(i!=n) MakeG(n,i);
for(int i=n+1;i<=n+10;i++) MakeG(n+11,i);
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) MakeG(i,n+k+1);
for(int i=1;i<=8;i+=2) MakeG(n+i,n+i+2);
MakeG(n+9,n+1);
for(int i=2;i<=8;i+=2) MakeG(n+i,n+i+2);
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1020;
vector<int>v[maxn];
int val[maxn], marc[maxn];
int arestas[maxn][maxn];
int dfs(int u, int lim){
marc[u]++;
int ret=0;
for(int viz : v[u]){
if(viz==lim||arestas[viz][lim]==0) continue;
if(marc[viz]){
ret++;
continue;
}
ret++;
ret+=dfs(viz,lim);
}
return ret;
}
void Bob( int N, int M, int C[], int D[] ){
for(int i=0;i<M;i++){
arestas[C[i]][D[i]]=arestas[D[i]][C[i]]=1;
v[C[i]].push_back(D[i]);
v[D[i]].push_back(C[i]);
}
int n=N-12;
int sb=0;
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
int m=M-n-20-sb-9;
InitMap(n,m);
int pai;
for(int i=0;i<N;i++) if(v[i].size()==N-2) pai=i;
int especial;
for(int i=0;i<N;i++){
int aux=lower_bound(v[pai].begin(),v[pai].end(),i)-v[pai].begin();
if(v[pai][aux]!=i) especial=i;
}
vector<int>bit;
vector<pair<int,int>> bit_par, bit_imp;
for(int x : v[especial]) bit.push_back(x);
for(int x : bit){
memset(marc,0,sizeof(marc));
int aux=dfs(x,especial);
if(aux==8) bit_imp.push_back({v[x].size(),x});
else bit_par.push_back({v[x].size(),x});
}
sort(bit_par.begin(),bit_par.end()); sort(bit_imp.begin(),bit_imp.end());
reverse(bit_par.begin(),bit_par.end()); reverse(bit_imp.begin(),bit_imp.end());
int cnt=0;
for(pair<int,int> p : bit_par){
int x=p.second;
for(int y : v[x]) val[y]|=(1<<cnt);
cnt+=2;
}
cnt=1;
for(pair<int,int> p : bit_imp){
int x=p.second;
for(int y : v[x]) val[y]|=(1<<cnt);
cnt+=2;
}
for(int x : bit) marc[x]++;
marc[pai]++; marc[especial]++;
for(int i=0;i<N;i++){
if(marc[i]) continue;
for(int x : v[i]) if(x>i&&marc[x]==0) MakeMap(val[x],val[i]);
}
}