This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
mt19937 rngA(time(nullptr));
vpi ordA(int N) {
vpi B(10); for(int i = 0; i < 10; i++) {
B[i] = mp(i, 0);
}
for(int i = 0; i < N; i++) {
for(int b = 0; b < N; b++) if ((i >> b) & 1) B[b].s++;
}
shuffle(begin(B), end(B), rngA);
return B;
}
const int EX = 12;
void Alice(int N, int M, int A[], int B[]){
int EX1 = N + EX - 2;
int EX2 = N + EX - 1;
vpi E;
for(int i = 0; i < M; i++) {
E.pb(mp(A[i], B[i]));
}
for(int i = 0; i < N; i++) {
E.pb(mp(i, EX2));
for(int b = 0; b < 10; b++) if ((i >> b) & 1) {
E.pb(mp(N + b, i));
}
}
vpi ORD = ordA(N);
// for(auto& x : ORD) cout << "( " << x.f << ", " << x.s << " ) ";
// cout << endl;
for(int i = 1; i < sz(ORD); i++) {
E.pb(mp(ORD[i-1].f + N, ORD[i].f + N));
}
E.pb(mp(ORD.back().f + N, EX2));
E.pb(mp(EX1, EX2));
for(int i = 0; i < sz(ORD); i++) {
E.pb(mp(EX1, ORD[i].f + N));
}
InitG(N + EX, sz(E));
for(int i = 0; i < sz(E); i++) {
// cout << i << " " << E[i].f << " " << E[i].s << endl;
// if (count(begin(E), end(E), E[i]) > 1) cout << "******" << endl;
MakeG(i, E[i].f, E[i].s);
}
}
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
mt19937 rngB(time(nullptr));
vpi ordB(int N) {
vpi B(10); for(int i = 0; i < 10; i++) {
B[i] = mp(i, 0);
}
for(int i = 0; i < N; i++) {
for(int b = 0; b < N; b++) if ((i >> b) & 1) B[b].s++;
}
shuffle(begin(B), end(B), rngB);
return B;
}
const int EX = 12;
void Bob(int N, int M, int A[], int B[]){
V<vi> adj(N);
for(int i = 0; i < M; i++) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
vpi ORD = ordB(N - EX); int K = sz(ORD);
for(int i = 0; i < K; i++) ORD[i].s += 2 + (i != 0);
ORD.pb(mp(-1, 2 + N - EX)); K++;
// for(auto& x : ORD) cout << "( " << x.f << ", " << x.s << " ) ";
// cout << endl;
vi stk = {}, alive(N, 0);
V<vi> vis(N, vi(K + 1));
V<vi> ans;
function<void(int, int)> find = [&](int u, int d) {
// cout << u << " " << d << " => " << sz(adj[u]) << endl;
stk.pb(u);
if (d == K) {
// cout << "FOUND" << endl;
ans.pb(stk);
} else {
for(auto& v : adj[u]) if (alive[v] && count(begin(stk), end(stk), v) == 0) {
// cout << "E: " << u << " -> " << v << " => " << sz(adj[v]) << " = " << ORD[d].s << " -> " << vis[v][d + 1] << endl;
// cout << endl;
if (sz(adj[v]) == ORD[d].s) {
find(v, d + 1);
}
}
}
stk.pop_back();
};
for(int i = 0; i < N; i++) {
if (sz(adj[i]) == K) {
// cout << i << endl;
vis[i] = vi(K + 1, 0);
// cout << "ALIVE" << endl;
for(auto x : adj[i]) {
// cout << x << " ";
alive[x] = 1; vis[x] = vi(K + 1, 0);
}
// cout << endl;
find(i, 0);
for(auto x : adj[i]) alive[x] = 0;
}
}
for(auto& x : ans) {
for(auto& v : x) cout << v << " ";
cout << endl;
}
assert(sz(ans) == 1);
// cout << sz(ans) << endl;
vi BITS(K); vi X(N);
for(auto& x : ans.front()) X[x] = -1;
for(int i = 1; i < sz(ans.front()) - 1; i++) {
BITS[ORD[i - 1].f] = ans.front()[i];
// cout << ORD[i - 1].f << " " << ans.front()[i] << endl;
}
// for(auto& x : BITS) cout << x << " ";
// cout << endl;
for(int i = 0; i < K-1; i++) {
for(auto& x : adj[BITS[i]]) {
if (X[x] == -1) continue;
X[x] ^= (1 << i);
}
}
vpi E;
for(int u = 0; u < N; u++) {
int U = X[u];
if (U == -1) continue;
for(auto& v : adj[u]) {
int V = X[v];
if (V == -1) continue;
if (U < V) {
// cout << U << " " << V << endl;
E.pb(mp(U, V));
}
}
}
InitMap(N - EX, sz(E));
for(int i = 0; i < sz(E); i++) MakeMap(E[i].f, E[i].s);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |