#include "Alicelib.h" # include <iostream> # include <vector> # include <algorithm> using namespace std; void Alice( int N, int M, int A[], int B[] ) { int n=N,m=M; vector<pair<int,int>> edges; for(int i=0;i<m;i++) edges.push_back({A[i],B[i]}); for(int i=0;i+1<=9;i++) edges.push_back({n+i,n+i+1}); for(int i=0;i<=9;i++) edges.push_back({n+i,n+10}); edges.push_back({n+10,n+11}); int num=2; for(int i=0;i<n;i++) { num++; while(__builtin_popcount(num)<=1) num++; //cout<<i<<" is represented by:"<<num<<"\n"; for(int bit=0;bit<=9;bit++) { if((num&(1<<bit))>0) edges.push_back({i,n+bit}); } } int sz=edges.size(); InitG(n+12,sz); for(int i=0;i<sz;i++) MakeG(i,edges[i].first,edges[i].second); }

#include "Boblib.h" #include <cassert> #include <cstdio> # include <iostream> # include <vector> # include <algorithm> using namespace std; const int MAX=1024; vector<int> adj[MAX]; int deg[MAX]; bool spec[MAX]; bool vis[MAX]; int cnt_spec[MAX]; int number[MAX]; int rep[MAX]; void Bob( int V, int U, int C[], int D[] ) { for(int i=0;i<U;i++) { int u=C[i],v=D[i]; adj[u].push_back(v); adj[v].push_back(u); deg[u]++; deg[v]++; } //for(int i=0;i<V;i++) cout<<i<<":"<<deg[i]<<"\n"; int s=0; for(int i=0;i<V;i++) { if(deg[i]==1) { s=i; break; } } s=adj[s][0]; for(int nxt: adj[s]) { if(deg[nxt]!=1) { spec[nxt]=1; } } for(int i=0;i<V;i++) { if(spec[i]) { for(int nxt: adj[i]) { if(spec[nxt]) cnt_spec[i]++; } } } vector<int> bits; int curr=-1; for(int i=0;i<V;i++) { if(spec[i] and cnt_spec[i]==1) { if(curr==-1) curr=i; else if(deg[curr]<deg[i]) curr=i; } } for(int i=0;i<10;i++) { bits.push_back(curr); vis[curr]=1; if(i==9) break; for(int nxt: adj[curr]) { if(spec[nxt] and !vis[nxt]) { curr=nxt; break; } } } spec[s]=1; //for(int x: bits) cout<<x<<" "; //cout<<"\n"; for(int bit=0;bit<10;bit++) { curr=bits[bit]; for(int nxt: adj[curr]) { if(!spec[nxt]) number[nxt]+=(1<<bit); } } int num=2; for(int i=0;i<V-12;i++) { num++; while(__builtin_popcount(num)<=1) num++; rep[num]=i; } vector<pair<int,int>> edges; for(int i=0;i<U;i++) { int u=C[i],v=D[i]; if(!spec[u] and !spec[v]) edges.push_back({rep[number[u]],rep[number[v]]}); } int sz=edges.size(); //cout<<"->"<<V-12<<" "<<sz<<"\n"; InitMap(V-12,sz); for(int i=0;i<sz;i++) MakeMap(edges[i].first,edges[i].second); }