Submission #989530

#	Time	Username	Problem	Language	Result	Execution time	Memory
989530		GrindMachine	Airline Route Map (JOI18_airline)	C++17	100 / 100	439 ms	29584 KiB

Alice

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read some comments about the solution long back, dont really remember much from there (except that we had to somehow encode the bits of each node)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Alicelib.h"

void Alice( int n, int m, int A[], int B[] ){
	// InitG( 4, 3 );
	// MakeG( 0, 1, 2 );
	// MakeG( 1, 1, 3 );
	// MakeG( 2, 2, 3 );

    if(n == 1){
        InitG(1,0);
        return;
    }

    if(n == 2){
        InitG(2,m);
        if(m){
            MakeG(0,A[0],B[0]);
        }
        return;
    }

    if(n == 3){
        int val = 0;
        int b = 0;
        set<pii> edges;
        rep(i,m){
            int u = A[i], v = B[i];
            if(u > v) swap(u,v);
            edges.insert({u,v});
        }

        rep(u,n){
            for(int v = u+1; v < n; ++v){
                if(edges.count({u,v})){
                    val |= (1<<b);
                }
                b++;    
            }
        }

        InitG(9,val);
        rep1(i,val){
            MakeG(i-1,0,i);
        }

        return;
    }

    vector<pii> edges;
    vector<int> deg(n+15);

    auto add_edge = [&](int u, int v){
        edges.pb({u,v});
        deg[u]++, deg[v]++;
    };

    rep(i,m){
        add_edge(A[i],B[i]);
    }

    rep(i,n){
        rep(bit,10){
            if((i+1)&(1<<bit)){
                add_edge(i,n+bit);
            }
        }
    }

    rep(i,n){
        add_edge(i,n+10);
    }

    add_edge(n+10,n+11);

    rep(bit,9){
        add_edge(n+bit,n+bit+1);
    }

    rep(i,n){
        if(deg[i] == n+1){
            add_edge(i,n+11);
        }
    }

    InitG(n+12,sz(edges));

    // rep(i,n+12){
    //     cout << deg[i] << " ";
    // }
    // cout << endl;

    rep(i,sz(edges)){
        MakeG(i,edges[i].ff,edges[i].ss);
    }
}

Bob

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read some comments about the solution long back, dont really remember much from there (except that we had to somehow encode the bits of each node)

*/

const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Boblib.h"

vector<int> adj[N];

void Bob( int n, int m, int C[], int D[] ){
	// InitMap( 4, 3 );
	// MakeMap( 0, 1 );
	// MakeMap( 0, 2 );
	// MakeMap( 0, 3 );

	if(n == 1){
		InitMap(1,0);
		return;
	}

	if(n == 2){
		InitMap(2,m);
		if(m){
			MakeMap(0,1);
		}
		return;
	}

	if(n == 9){
		vector<pii> edges;
		rep(bit,3){
			if(m&(1<<bit)){
				if(bit == 0){
					edges.pb({0,1});
				}
				else if(bit == 1){
					edges.pb({0,2});
				}
				else{
					edges.pb({1,2});
				}
			}
		}

		InitMap(3,sz(edges));
		for(auto [u,v] : edges){
			MakeMap(u,v);
		}
		
		return;
	}

	int on = n-12;

	vector<int> deg(n);
	rep(i,m){
		int u = C[i], v = D[i];
		deg[u]++, deg[v]++;
		adj[u].pb(v), adj[v].pb(u);
	}

	vector<bool> bad(n);

	rep(i,n){
		if(deg[i] == on+1){
			bad[i] = 1;
			trav(j,adj[i]){
				bad[j] = 1;
			}
		}
	}

	pii smallest = {inf1,inf1};
	rep(i,n){
		if(!bad[i]){
			pii px = {deg[i],i};
			amin(smallest,px);
		}
	}

	int curr = smallest.ss;
	vector<int> bits;
	while(curr != -1){
		bits.pb(curr);
		bad[curr] = 1;
		int nxt = -1;
		trav(j,adj[curr]){
			if(!bad[j]){
				assert(nxt == -1);
				nxt = j;
			}
		}

		curr = nxt;
	}

	reverse(all(bits));

	vector<bool> is_bit(n);
	trav(i,bits) is_bit[i] = 1;
	assert(sz(bits) == 10);

	// trav(i,bits){
	// 	cout << deg[i] << endl;
	// }

	vector<int> id(n);

	rep(i,sz(bits)){
		int u = bits[i];
		trav(v,adj[u]){
			if(is_bit[v]) conts;
			id[v] |= (1<<i);
		}
	}

	vector<pii> edges;

	rep(i,m){
		int u = C[i], v = D[i];
		if(id[u] and id[v]){
			edges.pb({id[u],id[v]});
		}
	}	

	InitMap(on,sz(edges));
	for(auto [u,v] : edges){
		u--, v--;
		MakeMap(u,v);
	}
}

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