Submission #211164

#	Time	Username	Problem	Language	Result	Execution time	Memory
211164		Alexa2001	Airline Route Map (JOI18_airline)	C++17	37 / 100	697 ms	43272 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

/// 11:18


static vector<pair<int,int>> edges;

static void add_edge(int x, int y)
{
    edges.push_back({x, y});
}

void Alice( int N, int M, int A[], int B[] )
{
    int S1, S2;

    S1 = N+10;
    S2 = N+11;

    add_edge(S1, S2);

    int i, j;
    for(i=0; i<M; ++i)
        add_edge(A[i], B[i]);

    for(i=0; i<N; ++i)
        for(j=0; j<10; ++j)
            if(i & (1<<j))
                add_edge(i, N+j);

    for(i=0; i<10; ++i)
    {
        add_edge(N+i, S1);
        add_edge(N+i, S2);

        if(i) add_edge(N+i, N+i-1);
    }
    add_edge(N+1, N+3);

    InitG(N+12, edges.size());
    int nr = 0;
    for(auto it : edges) MakeG(nr++, it.first, it.second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;

static int n, V, P[1005];
static vector<pair<int,int>> edges;
static vector<vector<int>> v;
static bitset<1005> bad;


static void add_edge(int x, int y)
{
    edges.push_back({x, y});
}

bool sortt(vector<int> &p)
{
    vector<vector<int>> gr(V);

    for(auto it : p)
        for(auto it2 : p)
            if(find(v[it].begin(), v[it].end(), it2) != v[it].end())
                gr[it].push_back(it2);

    vector<int> sp;
    for(auto it : p)
        if(gr[it].size() == 3) sp.push_back(it);

    if(sp.size() != 2) return 0;

    for(auto it : p)
        if(gr[it].size() != 2 && gr[it].size() != 3 && gr[it].size() != 1) return 0;

    int node = sp[0];
    gr[node].erase(find(gr[node].begin(), gr[node].end(), sp[1]));
    node = sp[1];
    gr[node].erase(find(gr[node].begin(), gr[node].end(), sp[0]));

    vector<int> vec[2];

    for(int step = 0; step < 2; ++step)
    {
        int prv = sp[0];
        node = gr[sp[0]][step];

        while(gr[node].size() == 2)
        {
            vec[step].push_back(node);
            int prr = node;
            node = gr[node][0] ^ gr[node][1] ^ prv;
            prv = prr;
        }

        vec[step].push_back(node);
    }

    if(vec[0].size() > vec[1].size()) swap(vec[0], vec[1]);
    reverse(vec[0].begin(), vec[0].end());

    p.clear();
    p.insert(p.end(), vec[0].begin(), vec[0].end());
    p.insert(p.end(), sp[0]);
    p.insert(p.end(), vec[1].begin(), vec[1].end());

    return 1;
}

bool Try(int A, int B)
{
    if(v[A].size() != 11 || v[B].size() != 11) return 0;

    vector<int> p = v[A];
    p.erase(find(p.begin(), p.end(), B));

    for(auto it : p)
        if(find(v[B].begin(), v[B].end(), it) == v[B].end()) return 0;

    int sum = 0, i, j;
    for(i=0; i<n; ++i)
        for(j=0; j<10; ++j)
            if(i & (1<<j))
                ++sum;

    sum += 20 + 20;

    int sum2 = 0;

    for(auto it : p)
        sum2 += v[it].size();

    if(sum != sum2)  return 0;

    bad.reset();
    edges.clear();

    bad[A] = bad[B] = 1;
    for(auto it : p) bad[it] = 1;

    for(i=0; i<V; ++i)
        for(auto it : v[i])
            if(!bad[i] && !bad[it] && i < it)
                add_edge(i, it);

    if(!sortt(p)) return 0;

    vector<int> where(V);

    for(i=0; i<10; ++i)
        where[p[i]] = i;

    vector<int> all;

    for(i=0; i<V; ++i)
        if(!bad[i])
        {
            P[i] = 0;
            for(auto it : v[i])
                if(bad[it])
                    P[i] ^= (1<<where[it]);
            all.push_back(P[i]);
        }

    sort(all.begin(), all.end());
    assert(all.size() == n);

    for(i=0; i<n; ++i)
        if(all[i] != i) return 0;

    InitMap(n, edges.size());
    for(auto it : edges)
        MakeMap(P[it.first], P[it.second]);
    return 1;
}

void Bob( int _V, int U, int C[], int D[] )
{
    V = _V;
    n = V - 12;

    int i;
    v.resize(V);
    for(i=0; i<U; ++i)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
    }

    for(i=0; i<V; ++i)
        for(auto it : v[i])
            if(Try(i, it)) return;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Bob.cpp:2:
Bob.cpp: In function 'bool Try(int, int)':
Bob.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(all.size() == n);
            ~~~~~~~~~~~^~~~

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