#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define INFLL 1000000000000000100ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
#define mid(x,y) (((x)+(y))>>1)
static vector<ii> e;
static int n,m,bits;
static int deg[2005];
static void add_directed_edge(int a,int b) {
//printf("%d %d\n", a,b);
deg[a]++;
deg[b]++;
e.pb(mp(a,b));
}
static void add_edge(int a,int b) {
//printf("%d %d\n", a,b);
if (rand()%2) swap(a,b);
deg[a]++;
deg[b]++;
e.pb(mp(a,b));
}
static void make() {
InitG(n+bits+2,sz(e));
for (int i=0;i<sz(e);i++) {
MakeG(i,e[i].first,e[i].second);
}
}
void Alice(int N, int M, int A[], int B[]) {
srand(83942);
n=N;
m=M;
for (int i=0;i<M;i++) {
add_edge(A[i],B[i]);
}
for (int i=0;i<n;i++) {
for (int j=0;j<10;j++) {
if (i&(1<<j)) {
add_edge(i,N+j);
}
}
}
for (int k=1;k<=10;k++) {
if ((1<<k)>=n) {
bits=k;
break;
}
}
//printf("= %d\n", bits);
for (int j=1;j<bits;j++) {
add_edge(N+j-1,N+j);
}
for (int i=0;i<n;i++) {
add_directed_edge(N+bits,i);
add_directed_edge(N+bits+1,i);
}
//add_directed_edge(N+bits,N+bits+1);
add_directed_edge(N+bits+1,N);
make();
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define INFLL 1000000000000000100ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
#define mid(x,y) (((x)+(y))>>1)
static int v,u,n,bits;
static int out[2005];
static int r1=-1,r2=-1,head=-1;
static set<int> mark;
static vector<int> h;
static vector<ii> edge;
static vector<int> adj[2005];
static bool vis[2005];
void dfs(int x) {
//printf("== %d\n", x);
vis[x]=1;
h.pb(x);
for (int y:adj[x]) {
if (vis[y]) continue;
if (mark.find(y)==mark.end()) continue;
dfs(y);
}
}
static int idx[2005];
static void add_edge(int a,int b) {
edge.pb(mp(a,b));
}
static void answer() {
InitMap(n,sz(edge));
for (ii x:edge) {
MakeMap(x.first,x.second);
}
}
static bool ingraph(int x) {
if (x==r1 || x==r2) return 0;
if (mark.find(x)!=mark.end()) return 0;
return 1;
}
void Bob( int V, int U, int C[], int D[] ){
v=V;
u=U;
for (int k=1;k<=10;k++) {
if ((1<<k)>=(v-k-2)) {
bits=k;
break;
}
}
n=v-bits-2;
//printf("= %d\n", bits);
for (int i=0;i<u;i++) {
adj[C[i]].pb(D[i]);
adj[D[i]].pb(C[i]);
out[C[i]]++;
}
for (int i=0;i<v;i++) {
//printf("* %d\n", out[i]);
if (out[i]==n) {
//assert(r1==-1);
r1=i;
}
if (out[i]==n+1) {
//assert(r2==-1);
r2=i;
}
}
assert(r1!=-1);
assert(r2!=-1);
for (int i=0;i<v;i++) mark.insert(i);
mark.erase(r1);
mark.erase(r2);
for (int x:adj[r1]) {
mark.erase(x);
}
assert(sz(mark)==bits);
for (int x:adj[r2]) {
if (mark.find(x)!=mark.end()) {
head=x;
}
}
assert(head!=-1);
dfs(head);
//printf("%d %d %d\n", r1,r2,head);
assert(sz(h)==bits);
for (int i=0;i<bits;i++) {
for (int x:adj[h[i]]) {
if (!ingraph(x)) continue;
idx[x]|=(1<<i);
}
}
for (int i=0;i<v;i++) {
if (!ingraph(i)) continue;
for (int x:adj[i]) {
if (!ingraph(x)) continue;
if (x>i) {
add_edge(idx[i],idx[x]);
}
}
}
answer();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
736 ms |
34808 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
