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 "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) (int)(a).size()
vector <int> C, D;
void Alice(int N, int M, int A[], int B[]){
for (int i = 0; i < M; i++){
C.push_back(A[i]);
D.push_back(B[i]);
}
for (int i = 0; i < N; i++){
for (int j = 0; j < 10; j++)
if (((i+1)>>j)&1){
C.push_back(i);
D.push_back(N+j);
}
}
for (int i = 0; i < 10; i++){
C.push_back(N+10);
D.push_back(N+i);
}
for (int i = 0; i+1 < 10; i++){
C.push_back(N+i);
D.push_back(N+i+1);
}
for (int i = 0; i <= N; i++){
C.push_back(N+11);
D.push_back(i);
}
InitG(N+12, isz(C));
for (int i = 0; i < isz(C); i++){
MakeG(i, C[i], D[i]);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) (int)(a).size()
int N, deg[1024], b[10];
bitset <1024> adj[1024];
vector <int> G[1024], ansA, ansB;
int id[1024];
bool check(int x, int y){
if (x == y) return 0;
if (deg[x] != 10) return 0;
if (deg[y] != N+1) return 0;
if (adj[x][y]) return 0;
if ((adj[x]&adj[y]).count() != 1) return 0;
for (int v : G[x]){
if (adj[y][v]) b[0] = v;
}
for (int i = 1; i < 10; i++){
for (int v : G[x])
if (adj[b[i-1]][v] && (i-2 < 0 || v != b[i-2])) b[i] = v;
}
for (int i = 1; i <= N; i++) id[i] = -1;
for (int i = 0; i < N+12; i++){
if (i == x || i == y || adj[x][i]) continue;
int tmp = 0;
for (int j = 0; j < 10; j++)
if (adj[i][b[j]]) tmp += (1<<j);
if (tmp < 1 || tmp > N) return 0;
if (id[tmp] != -1) return 0;
id[tmp] = i;
}
for (int i = 1; i < N; i++)
for (int j = i+1; j <= N; j++)
if (adj[id[i]][id[j]]){
ansA.push_back(i-1);
ansB.push_back(j-1);
}
InitMap(N, isz(ansA));
for (int i = 0; i < isz(ansA); i++)
MakeMap(ansA[i], ansB[i]);
return 1;
}
void Bob(int V, int U, int C[], int D[]){
N = V-12;
for (int i = 0; i < U; i++){
adj[C[i]][D[i]] = 1;
adj[D[i]][C[i]] = 1;
G[C[i]].push_back(D[i]);
G[D[i]].push_back(C[i]);
deg[C[i]]++;
deg[D[i]]++;
}
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (check(i, j)) return;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |