Submission #891394

#	Time	Username	Problem	Language	Result	Execution time	Memory
891394		boris_mihov	Airline Route Map (JOI18_airline)	C++17	Compilation error	0 ms	0 KiB

Alice

#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 );
}

Bob

#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 (stderr)

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)
      |                      ~~^~~~~~~~~~~~~~