Submission #1163940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163940		steveonalex	Two Transportations (JOI19_transportations)	C++20	100 / 100	315 ms	48904 KiB

Azer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}

//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

#include "Azer.h"

const int INF = 1e9 + 69;

struct Edge{
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};

struct P{
    int i, w;
    P(int i = 0, int w = 0): i(i), w(w){}
};

struct compare{
    bool operator () (P a, P b){return a.w > b.w;}
};


int DecodeSignal(vector<bool> signal){
    int ans = 0;
    for(int i = 0; i < (int) signal.size(); ++i) ans += MASK(i) * signal[i];
    return ans;
}

int n1, ma1;
vector<bool> infoA;
vector<vector<P>> graph1;
vector<bool> visited1;
vector<int> dihh1;
priority_queue<P, vector<P>, compare> pq1;
bool accelerated_mode1;

void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    n1 = n; ma1 = 0; accelerated_mode1 = false;
    infoA.clear(); graph1.clear(); visited1.clear(); dihh1.clear();
    while(pq1.size()) pq1.pop();

    graph1.resize(n);
    for(int i = 0; i < m; ++i){
        graph1[u[i]].push_back(P(v[i], w[i]));
        graph1[v[i]].push_back(P(u[i], w[i]));
    }

    visited1.resize(n); dihh1.resize(n, INF);
    dihh1[0] = 0;
    visited1[0] = 1;

    pq1.push(P(2047, MASK(20) - 1));
    for(P v: graph1[0]) if (minimize(dihh1[v.i], dihh1[0] + v.w))
        pq1.push(P(v.i, dihh1[v.i]));

    int cur = pq1.top().w;
    minimize(cur, 511);
    for(int j = 0; j < 9; ++j) SendA(GETBIT(cur, j));
}

void ReceiveA(bool x){
    infoA.push_back(x);
    if (accelerated_mode1 == false){
        if (infoA.size() == 9){
            int cur = DecodeSignal(infoA);
            infoA.clear();
            cur += ma1;
            if (cur >= pq1.top().w){
                P u = pq1.top(); pq1.pop();
                if (u.i >= n1) return;
                if (!visited1[u.i]) {
                    visited1[u.i] = true;
                    minimize(dihh1[u.i], u.w);
                    maximize(ma1, u.w);
                    for(P v: graph1[u.i])
                        if (minimize(dihh1[v.i], dihh1[u.i] + v.w))
                            pq1.push(P(v.i, dihh1[v.i]));

                    for(int j = 0; j < 11; ++j) SendA(GETBIT(u.i, j));
                }

                while(true){
                    P u = pq1.top();
                    if (u.i >= n1) break;
                    if (visited1[u.i])
                        pq1.pop();
                    else break;
                }

                cur = pq1.top().w;
                cur -= ma1;
                minimize(cur, 511);
                for(int j = 0; j < 9; ++j) SendA(GETBIT(cur, j));
            }
            else{
                accelerated_mode1 = true;
                ma1 = cur;
            }
        }
    }
    else{
        if (infoA.size() == 11){
            int u = DecodeSignal(infoA);
            infoA.clear();

            if (!visited1[u]){
                visited1[u] = true;
                minimize(dihh1[u], ma1);
                for(P v: graph1[u])
                    if (minimize(dihh1[v.i], dihh1[u] + v.w))
                        pq1.push(P(v.i, dihh1[v.i]));
            }

            while(true){
                P u = pq1.top();
                if (u.i >= n1) break;
                if (visited1[u.i])
                    pq1.pop();
                else break;
            }

            int cur = pq1.top().w;
            cur -= ma1;
            minimize(cur, 511);

            for(int j = 0; j < 9; ++j) SendA(GETBIT(cur, j));
            accelerated_mode1 = false;
        }
    }
}

vector<int> Answer(){
    return dihh1;
}

Baijan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}

//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }


#include "Baijan.h"

const int INF = 1e9 + 69;

struct Edge{
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};

struct P{
    int i, w;
    P(int i = 0, int w = 0): i(i), w(w){}
};

struct compare{
    bool operator () (P a, P b){return a.w > b.w;}
};



int DecodeSignal(vector<bool> signal){
    int ans = 0;
    for(int i = 0; i < (int) signal.size(); ++i) ans += MASK(i) * signal[i];
    return ans;
}


int n2, ma2;
vector<bool> infoB;
vector<vector<P>> graph2;
vector<bool> visited2;
vector<int> dihh2;
priority_queue<P, vector<P>, compare> pq2;
bool accelerated_mode2;


void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    n2 = n; ma2 = 0; accelerated_mode2 = false;
    infoB.clear(); graph2.clear(); visited2.clear(); dihh2.clear();
    while(pq2.size()) pq2.pop();

    graph2.resize(n);
    for(int i = 0; i < m; ++i){
        graph2[u[i]].push_back(P(v[i], w[i]));
        graph2[v[i]].push_back(P(u[i], w[i]));
    }

    visited2.resize(n); dihh2.resize(n, INF);
    dihh2[0] = 0;
    visited2[0] = 1;

    pq2.push(P(2047, MASK(20) - 1));
    for(P v: graph2[0]) if (minimize(dihh2[v.i], dihh2[0] + v.w))
        pq2.push(P(v.i, dihh2[v.i]));

    int cur = pq2.top().w;
    minimize(cur, 511);
    for(int j = 0; j < 9; ++j) SendB(GETBIT(cur, j));
}

void ReceiveB(bool x){
    infoB.push_back(x);
    if (accelerated_mode2 == false){
        if (infoB.size() == 9){
            int cur = DecodeSignal(infoB);
            infoB.clear();
            cur += ma2;
            if (cur > pq2.top().w){
                P u = pq2.top(); pq2.pop();
                if (u.i >= n2) return;
                if (!visited2[u.i]) {
                    visited2[u.i] = true;
                    minimize(dihh2[u.i], u.w);
                    maximize(ma2, u.w);
                    for(P v: graph2[u.i])
                        if (minimize(dihh2[v.i], dihh2[u.i] + v.w))
                            pq2.push(P(v.i, dihh2[v.i]));

                    for(int j = 0; j < 11; ++j) SendB(GETBIT(u.i, j));
                }

                while(true){
                    P u = pq2.top();
                    if (u.i >= n2) break;
                    if (visited2[u.i])
                        pq2.pop();
                    else break;
                }

                cur = pq2.top().w;
                cur -= ma2;
                minimize(cur, 511);
                for(int j = 0; j < 9; ++j) SendB(GETBIT(cur, j));
            }
            else{
                accelerated_mode2 = true;
                ma2 = cur;
            }
        }
    }
    else{
        if (infoB.size() == 11){
            int u = DecodeSignal(infoB);
            infoB.clear();

            if (!visited2[u]){
                visited2[u] = true;
                minimize(dihh2[u], ma2);
                for(P v: graph2[u])
                    if (minimize(dihh2[v.i], dihh2[u] + v.w))
                        pq2.push(P(v.i, dihh2[v.i]));
            }

            while(true){
                P u = pq2.top();
                if (u.i >= n2) break;
                if (visited2[u.i])
                    pq2.pop();
                else break;
            }

            int cur = pq2.top().w;
            cur -= ma2;
            minimize(cur, 511);

            for(int j = 0; j < 9; ++j) SendB(GETBIT(cur, j));
            accelerated_mode2 = false;
        }
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16