Submission #298526

#	Time	Username	Problem	Language	Result	Execution time	Memory
298526		Mercenary	Airline Route Map (JOI18_airline)	C++14	100 / 100	683 ms	23144 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] ){
    int V = N + 12;
    int U = M + 9 + N + N + 10;
    for(int i = 0 ; i < N ; ++i){
        U += __builtin_popcount(i);
    }
    InitG(V , U);
    int nTime = 0;
    for(int i = 0 ; i < M ; ++i){
        MakeG(nTime++,A[i],B[i]);
    }
    for(int i = 0 ; i < N ; ++i){
        for(int j = 0 ; j < 10 ; ++j){
            if((i & (1 << j))){
                MakeG(nTime++,i,N+j);
            }
        }
    }
    for(int i = N ; i + 1 <= N + 9 ; ++i){
        MakeG(nTime++,i,i+1);
    }
    for(int i = 0 ; i < N ; ++i){
        MakeG(nTime++,N+10,i);
    }
    for(int i = 0 ; i < N + 10 ; ++i){
        MakeG(nTime++,N+11,i);
    }
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 20;
bitset<maxn> adj[maxn];

void Bob( int V, int U, int CC[], int DD[] ){
    int N = V - 12;
    int M = U - 9 - 2 * N - 10;
    for(int i = 0 ; i < N ; ++i){
        M -= __builtin_popcount(i);
    }
    InitMap(N,M);
    if(N <= 2){
        if(M > 0)MakeMap(0,1);
        return;
    }
    for(int i = 0 ; i < U ; ++i){
        adj[CC[i]][DD[i]] = 1;
        adj[DD[i]][CC[i]] = 1;
    }
    int A = 0 , B = 0 , C = 0;
    for(int i = 0 ; i < V ; ++i){
        if(adj[i].count() == N + 10){
            for(int j = 0 ; j < V ; ++j){
                if(i != j && adj[i][j] == 0 && adj[j].count() == N){
                    A = i , B = j;break;
                }
            }
        }
    }
    assert(A != B);
    vector<int> added(V , 0);
    for(int i = 0 ; i < V ; ++i){
        if(i != A && i != B && adj[B][i] == 0){
            added[i] = 1;
            C = i;
        }
    }
    vector<int> path;
    auto dfs = [&](int u , int par){
        while(true){
            bool ok = 0;
            path.push_back(u);
            for(int i = 0 ; i < V ; ++i){
                if(added[i] && par != i && adj[u][i]){
                    par = u,u = i;
                    ok = 1;
                    break;
                }
            }
            if(ok == 0)break;
        }
    };
    for(int i = 0 ; i < V ; ++i){
        if(adj[C][i] && added[i]){
            if(path.size() == 0){
                dfs(i , C);
                reverse(path.begin(),path.end());
                path.push_back(C);
            }else{
                dfs(i , C);
            }
        }
    }
//    for(auto c : path)cout << c << " ";
    assert(path.size() == 10);
    if(adj[path[0]].count() < adj[path.back()].count())reverse(path.begin(),path.end());
    vector<int> p(V , 0);
    for(int i = 0 ; i < 10 ; ++i){
        for(int j = 0 ; j < V ; ++j){
            if(j != A && added[j] == 0 && adj[path[i]][j]){
                p[j] |= (1 << i);
            }
        }
    }
    for(int i = 0 ; i < U ; ++i){
        auto valid = [&](int u){
            if(added[u] || u == A || u == B)return 0;
            return 1;
        };
        if(valid(CC[i]) && valid(DD[i])){
//            assert(p[CC[i]] == p[DD[i]]);
            MakeMap(p[CC[i]],p[DD[i]]);
        }
    }
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:25:27: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         if(adj[i].count() == N + 10){
      |            ~~~~~~~~~~~~~~~^~~~~~~~~
Bob.cpp:27:63: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |                 if(i != j && adj[i][j] == 0 && adj[j].count() == N){
      |                                                ~~~~~~~~~~~~~~~^~~~

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