Submission #969081

# Submission time Handle Problem Language Result Execution time Memory
969081 2024-04-24T13:19:42 Z steveonalex Airline Route Map (JOI18_airline) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#include "Alice.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

namespace Debug{
    void InitG(int n, int m){
        cerr << "Number of vertices and edges: " << n << " " << m << "\n";
    }

    void MakeG(int pos, int u, int v){
        cerr << u << " " << v << "\n";
    }
}
// using namespace Debug;

void Alice(int n, int m, int A[], int B[]){
    vector<pair<int, int>> edging;
    for(int i = 0; i<m; ++i) edging.push_back({A[i], B[i]});

    for(int j= 0; j < 10; ++j){
        for(int i = 0; i<n; ++i) if (GETBIT(i, j)){
            edging.push_back({i, n + j});
        }
    }

    for(int i = 0; i < n + 10; ++i) edging.push_back({i, n + 10});
    for(int i = n; i < n + 10; ++i) edging.push_back({i, n + 11});
    for(int j = 1; j < 10; ++j) edging.push_back({n + j - 1, n + j});

    InitG(n + 12, edging.size());
    for(int i = 0; i<edging.size(); ++i) MakeG(i, edging[i].first, edging[i].second);
}
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, m; cin >> n >> m;
//     int a[n], b[n];
//     for(int i = 0; i<m; ++i){
//         cin >> a[i] >> b[i];
//     }

//     Alice(n, m, a, b);
 
//     return 0;
// }
#include <bits/stdc++.h>
#include "Bob.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

namespace Debug{
    void InitMap(int n, int m){
        cerr << "Number of vertices and edges: " << n << " " << m << "\n";
    }

    void MakeMap(int u, int v){
        cerr << u << " " << v << "\n";
    }
}
// using namespace Debug;

int mex(vector<int> &A){
    for(int i = 0;; ++i) if (!binary_search(ALL(A), i))
        return i;
}

void dfs(int u, int p, vector<vector<int>> &graph, vector<int> &chain){
    chain.push_back(u);
    for(int v: graph[u]) if (v != p) dfs(v, u, graph, chain);
}

void Bob(int n, int m, int A[], int B[]){
    vector<vector<int>> graph(n);
    for(int i = 0; i<m; ++i){
        int u = A[i], v = B[i];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 0; i<n; ++i) sort(ALL(graph[i]));

    pair<int, int> ma = {-1, -1};
    for(int i = 0; i<n; ++i) maximize(ma, make_pair((int)graph[i].size(), i) );

    int x = ma.second;
    graph[x].push_back(x);
    sort(ALL(graph[x]));

    int y = mex(graph[x]);

    vector<vector<int>> sigma(n);
    for(int u: graph[y]){
        for(int v: graph[u]) if (binary_search(ALL(graph[y]), v)){
            sigma[u].push_back(v);
        }
    }

    vector<int> chain;
    for(int u: graph[y]){
        if (sigma[u].size() == 1){
            dfs(u, u, sigma, chain);
            break;
        }
    }

    if (graph[chain[0]].size() < graph[chain.back()].size()) reverse(ALL(chain));

    vector<int> sum(n);
    for(int i = 0; i<n; ++i) if (i == x || i == y || binary_search(ALL(graph[y]), i)) sum[i] = -1;
    for(int j = 0; j < 10; ++j){
        for(int v: graph[chain[j]]) if (v != x && v != y && !binary_search(ALL(graph[y]), v)){
            sum[v] += MASK(j);
        }
    }

    vector<pair<int, int>> edging;
    for(int i = 0; i<n; ++i) if (sum[i] != -1){
        for(int j: graph[i]) if (sum[j] != -1 && i < j){
            edging.push_back({sum[i], sum[j]});
        }
    }

    InitMap(n - 12, edging.size());
    for(pair<int, int> i: edging) MakeMap(i.first, i.second);
}
 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, m; cin >> n >> m;
//     int a[m], b[m];
//     for(int i = 0; i<m; ++i){
//         cin >> a[i] >> b[i];
//     }

//     Bob(n, m, a, b);
 
//     return 0;
// }

Compilation message

Alice.cpp:2:10: fatal error: Alice.h: No such file or directory
    2 | #include "Alice.h"
      |          ^~~~~~~~~
compilation terminated.

Bob.cpp:2:10: fatal error: Bob.h: No such file or directory
    2 | #include "Bob.h"
      |          ^~~~~~~
compilation terminated.