Submission #205664

#	Time	Username	Problem	Language	Result	Execution time	Memory
205664		stefdasca	Airline Route Map (JOI18_airline)	C++14	0 / 100	669 ms	30648 KiB

Alice

/*
    JOISC 18-Airline

    idea: https://ivaniscoding.wordpress.com/2018/08/27/communication-4-airline-route-map/
*/

#include "Alicelib.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

void Alice(int N, int M, int A[], int B[])
{
    vector<pair<int, int> >muchii;
    for(int i = 0; i < M; ++i)
        muchii.pb({A[i], B[i]});
    for(int i = 0; i <= 9; ++i)
    {
        for(int j = 0; j < N; ++j)
            if(j & (1<<i))
                muchii.pb({N + i, j});
        if(i < 9)
            muchii.pb({N + i, N + i + 1});
    }
    for(int j = 0; j < N; ++j)
        muchii.pb({N + 10, j});
    muchii.pb({N + 11, N + 10});
    InitG(N + 12, muchii.size());
    for (int i = 0; i < muchii.size(); i++)
        MakeG(i, muchii[i].fi, muchii[i].se);
}

Bob

/*
    JOISC 18-Airline

    idea: https://ivaniscoding.wordpress.com/2018/08/27/communication-4-airline-route-map/

*/

#include "Boblib.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

vector<int> v[1024];
int trueval[1024];
bool adj[1024][1024], bit[1024], is_bit[1024], viz[1024];

void Bob(int V, int U, int C[], int D[])
{
    for (int i = 0; i < U; i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
    }
    int special;
    for(int i = 0; i < V; i++)
        if(v[i].size() == 1 && v[v[i][0]].size() == V - 11)
        {
            special = v[i][0];
            break;
        }
    bit[special] = 1;
    int last_bit = special;
    for(int i = 0; i < V; i++)
        if(i != special && !adj[i][special])
        {
            is_bit[i] = 1;
            if(v[i].size() <= v[last_bit].size())
                last_bit = i;
        }
    for(int i = 9; i >= 0; i--)
    {
        viz[last_bit] = 1;
        for(int j = 0; j < v[last_bit].size(); ++j)
        {
            int nod = v[last_bit][j];
            trueval[nod] += (1 << i);
        }
        for(int j = 0; j < v[last_bit].size(); ++j)
        {
            int nod = v[last_bit][j];
            if(is_bit[nod] && !viz[nod])
            {
                last_bit = nod;
                break;
            }
        }
    }
    vector<pair<int, int> >muchii;
    for(int i = 0; i < V; i++)
        for(int j = i + 1; j < V; j++)
            if(adj[i][j] && !is_bit[i] && !is_bit[j])
                muchii.pb({trueval[i], trueval[j]});
    InitMap(V - 12, muchii.size());
    for(int i = 0; i < muchii.size(); ++i)
        MakeMap(muchii[i].fi, muchii[i].se);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < muchii.size(); i++)
                     ~~^~~~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:30:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size() == 1 && v[v[i][0]].size() == V - 11)
                                ~~~~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < v[last_bit].size(); ++j)
                        ~~^~~~~~~~~~~~~~~~~~~~
Bob.cpp:52:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < v[last_bit].size(); ++j)
                        ~~^~~~~~~~~~~~~~~~~~~~
Bob.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < muchii.size(); ++i)
                    ~~^~~~~~~~~~~~~~~
Bob.cpp:35:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
     bit[special] = 1;
     ~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 15
• Subtask 3: 0 / 63