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 <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define maxn 1111
#define maxK 4100
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mod 1000000007
#define debug(args...) //fprintf(stderr,args)
using namespace std;
#define dg dhbe
int dg[maxn];
void Alice( int N, int M, int A[], int B[] ){
vector<pii> v;
for(int i=0;i<M;i++){
v.pb({A[i],B[i]}), dg[A[i]]++, dg[B[i]]++;
}
for(int i=0;i<10;i++)
for(int j=0;j<N;j++)
if(j & (1<<i))
v.pb({i+N,j}), dg[i+N]++, dg[j]++;
for(int i=0;i<N+10;i++)
v.pb({N+10,i});
for(int i=N;i<N+10;i++)
v.pb({N+11,i});
for(int i=N+2;i<N+10;i++)
v.pb({N,i});
for(int i=N+1;i<N+9;i++)
v.pb({i,i+1});
InitG(N+12,v.size());
int bla = 0;
for(pii i : v)
MakeG(bla++, i.first,i.second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#define maxn 1111
#include <bits/stdc++.h>
#define maxK 4100
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mod 1000000007
#define debug(args...) //fprintf(stderr,args)
using namespace std;
int mrk[maxn];
int m2[maxn];
int dg[maxn];
vector<int> L[maxn];
int real_id[maxn];
int vis[maxn];
void go(int vx,int num,int p=-1){
//if(vis[vx]) return;
vis[vx] = 1;
for(int i : L[vx])
real_id[i] += num;
debug("go %d with %d\n",vx,num);
for(int i : L[vx])
if(mrk[i] == 1 && i != p)
go(i,2*num,vx);
}
void Bob( int V, int U, int C[], int D[] ){
for(int i=0;i<U;i++)
debug("+ %d %d\n",C[i],D[i]);
for(int i=0;i<V;i++) L[i].clear(), mrk[i] = dg[i] = vis[i] = m2[i] = real_id[i] = 0;
for(int i=0;i<U;i++){
dg[C[i]]++, dg[D[i]]++;
L[C[i]].pb(D[i]);
L[D[i]].pb(C[i]);
}
vector<int> id;
for(int i=0;i<V;i++)
id.pb(i);
sort(id.begin(), id.end(), [](int i,int j){
return dg[i] > dg[j];
});
debug("id %d (%d), %d(%d)\n",id[0],dg[id[0]],id[1],dg[id[1]]);
int x = id[0];
for(int i : L[x])
mrk[i] = 1;
int y = -1;
for(int i=0;i<V;i++)
if(mrk[i] == 0 && i != x) y = i;
assert(y != -1);
assert(dg[y] == 10);
for(int i : L[y])
mrk[i] = 2;
int z = -1;
for(int i=0;i<V;i++){
int t = 0;
for(int j : L[i])
if(mrk[j] == 2) t++;
if(t == 8 && mrk[i] == 2) z = i;
}
assert(z != -1);
for(int i : L[z])
m2[i] = 1;
debug("x %d y %d\n",x,y);
debug(": %d\n",z);
int uno = -1;
for(int i=0;i<V;i++)
if(mrk[i] == 2 && m2[i] == 0 && i != z)
uno = i;
assert(uno != -1);
for(int i : L[z])
real_id[i]++;
vis[z] = 1;
for(int i=0,k=2;i<9;i++,k*=2){
int nxt = -1;
debug(": %d\n",uno);
vis[uno] = 1;
for(int j : L[uno])
real_id[j] += k;
for(int j : L[uno])
if(mrk[j] == 2 && !vis[j])
nxt = j;
uno = nxt;
}
int n = V - 12;
//assert(dg[id[0]] == n + 5 && dg[id[1]] == n + 4 && dg[id[2]] < n + 4);
int ini = -1;
for(int i=0;i<V;i++) if(mrk[i] == 0 && i != id[0] && i != id[1]){
//assert(ini == -1);
ini = i;
}
//assert(ini >= 0);
go(ini,1);
for(int i=0;i<V;i++)
debug("mrk[%d] = %d, real_id = %d\n",i,mrk[i],real_id[i]);
vector<pii> ans ;
for(int i=0;i<U;i++)
if(mrk[C[i]] == 1 && mrk[D[i]] == 1){
debug("add %d %d -> %d %d\n",C[i],D[i],real_id[C[i]], real_id[D[i]]);
ans.pb({real_id[C[i]], real_id[D[i]]});
}
InitMap( V - 12, ans.size() );
for(pii i : ans)
MakeMap( i.first, i.second );
}
Compilation message (stderr)
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:131:6: warning: unused variable 'n' [-Wunused-variable]
131 | int n = V - 12;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |