#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
#define sz(x) int(x.size())
void Alice( int N, int M, int A[], int B[] )
{
int V = N + 10 + 2;
int U = 0;
vpii res;
for(int e = 0; e < M; e++)
{
res.push_back({A[e], B[e]});
}
for(int b = 0; b < 10; b++)
{
for(int i = 0; i < N; i++)
{
if(i & (1 << b))
{
// edge[N+b].push_back(i);
// // edge[i].push_back(N+b);
// U++;
res.push_back({N+b, i});
}
}
}
for(int b = 0; b <= 7; b++)
res.push_back({N+b, N+b+1});
res.push_back({N+6, N+9});
int bitroot = N+10;
for(int i = N; i < bitroot; i++)
{
// edge[bitroot].push_back(i);
// U++;
res.push_back({bitroot, i});
}
int flag = N+11;
for(int i = 0; i < bitroot; i++)
{
res.push_back({flag, i});
}
InitG(V, sz(res));
for(int e = 0; e < sz(res); e++)
{
MakeG(e, res[e].first, res[e].second);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
void Bob( int V, int U, int C[], int D[] )
{
int N = V - 12;
vvi edge(V, vi(V, 0));
vi edgelist[V];
vi deg(V, 0);
for(int e = 0; e < U; e++)
{
// edge[C[u]].push_back(D[u]);
// edge[D[u]].push_back(C[u]);
edge[C[e]][D[e]] = edge[D[e]][C[e]] = 1;
edgelist[C[e]].push_back(D[e]);
edgelist[D[e]].push_back(C[e]);
deg[C[e]]++;
deg[D[e]]++;
}
int flag = 0;
while(deg[flag] != V - 2) flag++;
int bitroot = 0;
while((bitroot == flag) || (edge[bitroot][flag]))
bitroot++;
vi isbit(V, 0);
vi bits;
for(int i = 0; i < V; i++)
{
if(edge[bitroot][i])
{
isbit[i] = 1;
bits.push_back(i);
}
}
vi bit_edgelist[V];
// cerr << "! " << sz(bits) << '\n';
vi bitdeg(V, 0);
for(int x = 0; x < sz(bits); x++)
{
for(int y = x+1; y < sz(bits); y++)
{
if(edge[ bits[x] ][ bits[y] ])
{
bitdeg[ bits[x] ]++;
bitdeg[ bits[y] ]++;
bit_edgelist[bits[x]].push_back(bits[y]);
bit_edgelist[bits[y]].push_back(bits[x]);
}
}
}
// for(int i = 0; i < V; i++) cerr << bitdeg[i] << ' ';
// cerr << '\n';
vi codedbit(10, -1);
codedbit[6] = 0;
while(bitdeg[codedbit[6]] != 3) codedbit[6]++;
vi visit(V, 0);
vvi bit_lists;
visit[codedbit[6]] = 1;
for(int z : bit_edgelist[codedbit[6]])
{
bit_lists.push_back({});
int p = z;
while(1)
{
visit[p] = 1;
bit_lists.back().push_back(p);
int newfound = -1;
for(int q : bit_edgelist[p])
{
if(visit[q]) continue;
newfound = q;
break;
}
if(newfound == -1) break;
p = newfound;
}
}
sort(bit_lists.begin(), bit_lists.end(), [] (vi f, vi g)
{
return sz(f) < sz(g);
});
codedbit[9] = bit_lists[0][0];
codedbit[7] = bit_lists[1][0];
codedbit[8] = bit_lists[1][1];
for(int k = 0; k < 6; k++)
codedbit[5 - k] = bit_lists[2][k];
// for(int i = 0; i < 10; i++) cerr << codedbit[i] << ' ';
// cerr << '\n';
vvi actual_edge(N, vi(N, 0));
vi actind(V, -1);
for(int i = 0; i < V; i++)
{
if(i == flag) continue;
if(i == bitroot) continue;
if(isbit[i]) continue;
// int actual_index;
actind[i] = 0;
for(int b = 0; b < 10; b++)
{
if(edge[i][codedbit[b]])
{
actind[i] += (1<<b);
}
}
}
int M = 0;
for(int i = 0; i < V; i++)
{
if(actind[i] == -1) continue;
for(int j = i+1; j < V; j++)
{
if(actind[j] == -1) continue;
if(edge[i][j] == 0) continue;
actual_edge[actind[i]][actind[j]] = actual_edge[ actind[j] ][ actind[i] ] = 1;
M++;
}
}
InitMap(N, M);
for(int i = 0; i < N; i++)
for(int j = i+1; j < N; j++)
if(actual_edge[i][j])
MakeMap(i, j);
}
Compilation message
Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:15:6: warning: unused variable 'U' [-Wunused-variable]
15 | int U = 0;
| ^
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:115:2: error: 'sort' was not declared in this scope; did you mean 'qsort'?
115 | sort(bit_lists.begin(), bit_lists.end(), [] (vi f, vi g)
| ^~~~
| qsort
