| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 47041 | vanogam | 항공 노선도 (JOI18_airline) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
vector<int> v[1102];
int d[1102][1102],f[1102],g[1102];
int k=0;
for(int i=0;i<U;i++){
//cout<<C[i]<<" "<<D[i]<<endl;
v[C[i]].push_back(D[i]);
v[D[i]].push_back(C[i]);
d[C[i]][D[i]]=1;
d[D[i]][C[i]]=1;
}
for(int i=0;i<V;i++){
sort(v[i].begin(),v[i].end());
//for(auto it:v[i]) cout<<i<<" "<<it<<endl;
}
for(int i=0;i<V;i++){
if(v[i].size()==V-2) {k=i;break;}
}
f[k]=-10;
g[k]=2;
for(auto it:v[k]) g[it]=1;
for(int i=0;i<V;i++){
if(!g[i]) {k=i;break;}
}g[k]=2;
f[k]=-10;
for(int i=0;i<V;i++){
if(!d[k][i]) g[i]=2;
}
for(int i=0;i<V;i++){
if(g[i]==2) continue;//cout<<"**"<<i<<"**";
for(int a=i+1;a<V;a++){
if(g[a]==2) continue;
if(d[i][a]){f[i]--;f[a]--;}
}
}
for(int i=0;i<V;i++){//cout<<f[i]<<"&";
if(f[i]==-4) {k=i;break;}
}
int xr=1,l=0;
for(int i=0;i<10;i++){
for(auto it:v[k]){
if(f[it]>=0) {f[it]+=xr;}
if(f[it]==-10) continue;//cout<<f[it]<<" ";
if(f[it]==-3 && f[k]!=-4) {l=it;}
if(f[it]==-2) {l=it;}
}//cout<<endl;
f[k]=-10;//cout<<f[0]<<"**"<<endl;
k=l;
xr*=2;
}
for(int i=0;i<V;i++){
if(f[i]>=0){
for(auto it:v[i]){
if(f[it]>=0) {d[i][it]=2;d[it][i]=2;}
}
}
}
int m=0;
for(int i=0;i<V;i++){
if(f[i]<0) continue;
for(int a=i+1;a<V;a++){
if(f[a]<0) continue;
if(d[i][a]==2) m++;
}
}//cout<<"**"<<m<<"**";
InitMap(V-12,m);
for(int i=0;i<V;i++){
if(f[i]<0) continue;
for(int a=i+1;a<V;a++){
if(f[a]<0) continue;
if(d[i][a]==2){MakeMap(f[i],f[a]);}
}
}
}
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
int a=0,u=0;
a+=N+10+10+M+12;
for(int i=0;i<N;i++){
a+=__builtin_popcount(i);
}
InitG( N+12, a );
for(int i=0;i<N;i++){
MakeG(u++,i,N+10);
//MakeG(u++,i,N+11);//cout<<"*";
}
for(int i=N;i<N+10;i++){
MakeG(u++,i,N+10);
MakeG(u++,i,N+11);
if(i!=N+9) MakeG(u++,i,i+1);
//else MakeG(u++,N,i+2);
}
MakeG(u++,N,N+5);
MakeG(u++,N,N+6);
MakeG(u++,N,N+7);
for(int i=0;i<M;i++) MakeG(u++,A[i],B[i]);
for(int i=0;i<N;i++){
for(int a=0;a<10;a++){
if(i&(1<<a)) MakeG(u++,i,N+a);
}
}
}