#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <assert.h>
#include <algorithm>
#include <random>
using namespace std;
#define MAX_N 1000
#define MAX_V 1500
#define ALICE 0
#define BOB 1
static int N, M, A[MAX_N*(MAX_N-1)/2], B[MAX_N*(MAX_N-1)/2];
static int V, U, C[MAX_V*(MAX_V-1)/2], D[MAX_V*(MAX_V-1)/2];
static int C_[MAX_V*(MAX_V-1)/2], D_[MAX_V*(MAX_V-1)/2];
static int N_, M_, A_[MAX_V*(MAX_V-1)/2], B_[MAX_V*(MAX_V-1)/2];
static int max_dif = 0;
void Alice( int N, int M, int A[], int B[] );
void Bob( int V, int U, int C[], int D[] );
bool used[MAX_V*(MAX_V-1)/2];
bool exist_edge[MAX_N][MAX_N];
bool used_edge[MAX_N][MAX_N];
int cnt_makemap;
void init(){
V = 0;
U = 0;
N_ = 0;
for(int i = 0 ; i < MAX_V*(MAX_V-1)/2 ; i ++){
used[i] = false;
}
for(int i = 0 ; i < MAX_N ; i ++){
for(int j = 0 ; j < MAX_N ; j ++){
exist_edge[i][j] = false;
used_edge[i][j] = false;
}
}
cnt_makemap = 0;
}
void WrongAnswer( int e ){
fprintf( stderr, "Wrong Answer [%d]\n", e );
exit( 0 );
}
void input_check( int e , int WA_num ){
if( e == -1 ){
WrongAnswer( WA_num );
}
}
void InitG( int in_V, int in_U ){
if(V != 0)WrongAnswer(6);
if(in_V <= 0)WrongAnswer(1);
if(in_V > MAX_V)WrongAnswer(1);
V = in_V;
if(in_U < 0)WrongAnswer(2);
if(in_U > V*(V-1)/2)WrongAnswer(2);
U = in_U;
}
void MakeG( int pos, int in_C, int in_D ){
if(V == 0)WrongAnswer(7);
if(pos < 0)WrongAnswer(3);
if(pos >= U)WrongAnswer(3);
if(used[pos])WrongAnswer(4);
used[pos] = true;
if(in_C < 0)WrongAnswer(5);
if(in_C >= V)WrongAnswer(5);
if(in_D < 0)WrongAnswer(5);
if(in_D >= V)WrongAnswer(5);
if(in_C == in_D)WrongAnswer(5);
C[pos] = in_C;
D[pos] = in_D;
}
void InitMap( int in_N, int in_M ){
if(N_ != 0)WrongAnswer(15);
N_ = in_N;
if(N_ != N)WrongAnswer(10);
M_ = in_M;
if(M_ != M)WrongAnswer(11);
}
void shuffle(){
std::random_device rnd;
std::mt19937 mt(rnd());
static pair<int,int> p[MAX_V];
for(int i = 0 ; i < V ; i ++){
p[i] = pair<int,int>( mt() , i );
}
sort(p,p+V);
static pair<int,int> q[MAX_V*(MAX_V-1)/2];
for(int i = 0 ; i < U ; i ++){
q[i] = pair<int,int>( mt() , i );
}
sort(q,q+U);
for(int i = 0 ; i < U ; i ++){
C_[i] = p[C[q[i].second]].second;
D_[i] = p[D[q[i].second]].second;
}
for(int i = 0 ; i < U ; i ++){
C[i] = C_[i];
D[i] = D_[i];
}
}
void MakeMap( int in_A, int in_B ){
if(N_ == 0)WrongAnswer(16);
if(in_A < 0)WrongAnswer(12);
if(in_A >= N)WrongAnswer(12);
if(in_B < 0)WrongAnswer(12);
if(in_B >= N)WrongAnswer(12);
if(in_A == in_B)WrongAnswer(12);
if(in_A > in_B)swap(in_A,in_B);
if(!exist_edge[in_A][in_B])WrongAnswer(13);
if(used_edge[in_A][in_B])WrongAnswer(14);
used_edge[in_A][in_B] = true;
cnt_makemap ++;
}
int main( int argc, char** argv ){
init();
scanf("%d%d",&N,&M);
for(int i = 0 ; i < M ; i ++){
scanf("%d%d",&A[i],&B[i]);
}
Alice( N, M, A, B );
if(V == 0)WrongAnswer(8);
for(int i = 0 ; i < U ; i ++){
if(!used[i])WrongAnswer(8);
}
static bool edge_used[MAX_V][MAX_V];
for(int i = 0 ; i < MAX_V ; i ++){
for(int j = 0 ; j < MAX_V ; j ++){
edge_used[i][j] = false;
}
}
shuffle();
for(int i = 0 ; i < U ; i ++){
if(edge_used[C[i]][D[i]])WrongAnswer(9);
edge_used[C[i]][D[i]] = true;
edge_used[D[i]][C[i]] = true;
}
for(int i = 0 ; i < M ; i ++){
exist_edge[A[i]][B[i]] = true;
exist_edge[B[i]][A[i]] = true;
}
Bob( V, U, C, D );
if(cnt_makemap != M)WrongAnswer(17);
fprintf( stderr, "Accepted\n" );
fprintf( stderr, "V = %d\n", V );
}
#include "Boblib.h"
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 1012 + 10;
const int INF = 1e9;
int number[MAXN];
bool inReal[MAXN];
bool connected[MAXN][MAXN];
std::vector <std::pair <int,int>> edges;
std::vector <int> g[MAXN];
std::vector <int> logs;
int realLog[MAXN];
bool isLog[MAXN];
int deg[MAXN];
void dfs(int node, int par)
{
logs.push_back(node);
for (const int &u : g[node])
{
if (u == par)
{
continue;
}
if (isLog[u])
{
dfs(u, node);
}
}
}
void Bob( int V, int U, int C[], int D[] )
{
if (V <= 2)
{
if (U == 0)
{
InitMap(V, 0);
} else
{
InitMap(V, 1);
MakeMap(0, 1);
}
return;
}
for (int i = 0 ; i < U ; ++i)
{
g[C[i]].push_back(D[i]);
g[D[i]].push_back(C[i]);
deg[C[i]]++; deg[D[i]]++;
connected[C[i]][D[i]] = true;
connected[D[i]][C[i]] = true;
}
for (int i = 0 ; i < U ; ++i)
{
inReal[i] = true;
}
int log = 12;
int n = V - log - 3;
int root = -1;
for (int i = 0 ; i < V ; ++i)
{
if (deg[i] == V - 3)
{
root = i;
}
}
assert(root != -1);
int source = -1;
int pointing = -1;
for (int i = 0 ; i < V ; ++i)
{
if (i != root && !connected[i][root] && deg[i] == 1)
{
pointing = i;
}
if (i != root && !connected[i][root] && deg[i] == log)
{
source = i;
}
}
assert(source != -1);
assert(pointing != -1);
for (const int &u : g[source])
{
isLog[u] = true;
}
dfs(g[pointing][0], 0);
// assert(logs.size() == log);
for (int i = 0 ; i < log ; ++i)
{
inReal[logs[i]] = false;
realLog[logs[i]] = i;
}
inReal[root] = false;
inReal[source] = false;
inReal[pointing] = false;
for (int i = 0 ; i < V ; ++i)
{
if (!inReal[i])
{
continue;
}
for (int j = 0 ; j < log ; ++j)
{
if (connected[i][logs[j]])
{
number[i] |= (1 << j);
}
}
}
for (int i = 0 ; i < V ; ++i)
{
for (int j = i + 1 ; j < V ; ++j)
{
if (!inReal[i] || !inReal[j] || !connected[i][j])
{
continue;
}
edges.push_back({number[i], number[j]});
}
}
InitMap(n, edges.size());
for (int i = 0 ; i < edges.size() ; ++i)
{
MakeMap(edges[i].first, edges[i].second);
}
return;
}
Compilation message
Alice.cpp: In function 'int main(int, char**)':
Alice.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf("%d%d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~
Alice.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d%d",&A[i],&B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
Alice.cpp: At global scope:
Alice.cpp:18:12: warning: 'max_dif' defined but not used [-Wunused-variable]
18 | static int max_dif = 0;
| ^~~~~~~
Alice.cpp:17:43: warning: 'B_' defined but not used [-Wunused-variable]
17 | static int N_, M_, A_[MAX_V*(MAX_V-1)/2], B_[MAX_V*(MAX_V-1)/2];
| ^~
Alice.cpp:17:20: warning: 'A_' defined but not used [-Wunused-variable]
17 | static int N_, M_, A_[MAX_V*(MAX_V-1)/2], B_[MAX_V*(MAX_V-1)/2];
| ^~
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `init()':
Alice.cpp:(.text+0x4b0): multiple definition of `init()'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text+0x80): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o:(.bss+0x1e84a0): multiple definition of `used'; /tmp/ccKbHNLJ.o:(.bss+0x1e84a0): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o:(.bss+0xf4260): multiple definition of `exist_edge'; /tmp/ccKbHNLJ.o:(.bss+0xf4260): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o:(.bss+0x20): multiple definition of `used_edge'; /tmp/ccKbHNLJ.o:(.bss+0x20): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o:(.bss+0x0): multiple definition of `cnt_makemap'; /tmp/ccKbHNLJ.o:(.bss+0x0): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `WrongAnswer(int)':
Alice.cpp:(.text+0x520): multiple definition of `WrongAnswer(int)'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text+0xf0): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `input_check(int, int)':
Alice.cpp:(.text+0x550): multiple definition of `input_check(int, int)'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text+0x120): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `InitG(int, int)':
Alice.cpp:(.text+0x570): multiple definition of `InitG(int, int)'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text+0x140): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `MakeG(int, int, int)':
Alice.cpp:(.text+0x5d0): multiple definition of `MakeG(int, int, int)'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text+0x1a0): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `main':
Alice.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKbHNLJ.o:grader_alice.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccOlitVJ.o: in function `main':
Alice.cpp:(.text.startup+0x89): undefined reference to `Alice(int, int, int*, int*)'
/usr/bin/ld: Alice.cpp:(.text.startup+0x1a6): undefined reference to `Bob(int, int, int*, int*)'
/usr/bin/ld: /tmp/ccKbHNLJ.o: in function `main':
grader_alice.cpp:(.text.startup+0xa2): undefined reference to `Alice(int, int, int*, int*)'
collect2: error: ld returned 1 exit status
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0 ; i < edges.size() ; ++i)
| ~~^~~~~~~~~~~~~~
