Submission #185442

#	Time	Username	Problem	Language	Result	Execution time	Memory
185442		Akashi	Airline Route Map (JOI18_airline)	C++14	0 / 100	943 ms	35272 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

struct usu{
    int pos, x, y;
};

const int LG = 9;
vector <usu> edgeS;
void add_edge(int pos, int x, int y){
    edgeS.push_back({pos, x, y});
}

void Alice( int n, int m, int a[], int b[] ){
    for(int i = 0; i < m ; ++i) add_edge(i, a[i], b[i]);

    int nr = m - 1;
    for(int i = n; i <= n + LG ; ++i){
        add_edge(++nr, i, n + 10);
        add_edge(++nr, i, n + 11);
        if(i != n + LG) add_edge(++nr, i, i + 1);
    }
    for(int i = 0; i < n ; ++i){
        add_edge(++nr, i, n + 11);
        for(int j = 0; j <= LG ; ++j){
            if((1 << j) & i) add_edge(++nr, i, n + j + 1);
        }
    }

    InitG(n + 12, edgeS.size());
    for(auto it : edgeS) MakeG(it.pos, it.x, it.y);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

const int LG = 9;
int real_n;
int gr[1025], exp_gr[1025];
int real_id[1025];
bool viz[1025], ap[1025];
vector <int> v[1025];
vector <pair <int, int> > edges;

void find_bits(int n, int wh, int p){
    for(auto it : v[wh]){
        ap[it] = 1;
        v[it].erase(find(v[it].begin(), v[it].end(), wh));
        v[it].erase(find(v[it].begin(), v[it].end(), p));
        gr[it] -= 2;
    }
    int nr = LG;
    while(nr >= 0){
        int aux;
        for(auto nod : v[wh]){
            if(!ap[nod]) continue ;
            int cnt = 0;
            for(auto it : v[nod]) if(ap[it]) ++cnt;

            if(cnt <= 1 && gr[nod] - cnt == exp_gr[nr]){
                ap[nod] = 0;
                aux = nod;
                real_id[nod] = nr + real_n;
                break ;
            }
        }

        for(auto nod : v[wh]){
            if(find(v[nod].begin(), v[nod].end(), aux) != v[nod].end()){
                v[nod].erase(find(v[nod].begin(), v[nod].end(), aux));
                v[aux].erase(find(v[aux].begin(), v[aux].end(), nod));
                --gr[nod]; --gr[aux];
                break ;
            }
        }
        --nr;
    }

}

void Bob( int n, int m, int C[], int D[] ){
    real_n = n - 12;
    for(int i = 0; i < real_n ; ++i){
        for(int j = 0; j <= LG ; ++j)
            if((1 << j) & i) ++exp_gr[j];
    }

    for(int i = 0; i < m ; ++i){
        ++gr[C[i]];
        ++gr[D[i]];
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
    }

    int p, wh;
    for(int i = 0; i < n ; ++i) if(gr[i] == n - 2) {real_id[i] = n - 2; p = i; break ;}

    viz[p] = 1;
    for(auto it : v[p]) viz[it] = 1;
    for(int i = 0; i < n ; ++i) if(!viz[i]) {real_id[i] = n - 1; wh = i; break ;}

    memset(viz, 0, sizeof(viz));
    find_bits(n - 2, wh, p);

    for(auto nod : v[wh]){
        if(nod == p) continue ;
        int ad = real_id[nod] - real_n;
        int p = (1 << ad);
        for(auto it : v[nod]) real_id[it] += p;
    }

    for(int i = 0; i < n ; ++i){
        if(real_id[i] >= real_n) continue ;
        for(auto it : v[i]){
            if(real_id[i] < real_id[it] && real_id[it] < real_n)
                edges.push_back({real_id[i], real_id[it]});
        }
    }

    InitMap(real_n, edges.size());
    for(auto it : edges) MakeMap(it.first, it.second);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:66:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
     viz[p] = 1;
     ~~~~~~~^~~
Bob.cpp:71:14: warning: 'wh' may be used uninitialized in this function [-Wmaybe-uninitialized]
     find_bits(n - 2, wh, p);
     ~~~~~~~~~^~~~~~~~~~~~~~

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