제출 #1163859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163859		steveonalex	Two Transportations (JOI19_transportations)	C++20	0 / 100	145 ms	1092 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;}
};


P DecodeSignal(vector<bool> signal){
    P ans;
    for(int i = 0; i< 11; ++i) ans.i += signal[i] * MASK(i);
    for(int i = 0; i< 20; ++i) ans.w += signal[i+11] * MASK(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;

void SendSignalA(P v){
    bitset<11> u(v.i);
    bitset<9> w(v.w);
    for(int i = 0; i < 11; ++i) SendA(u[i]);
    for(int i = 0; i < 9; ++i) SendA(w[i]);
}


void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    n1 = n; ma1 = 0;
    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]));

    SendSignalA(pq1.top());
}

void ReceiveA(bool x){
    infoA.push_back(x);
    if (infoA.size() == 20){
        P cur = DecodeSignal(infoA);
        infoA.clear();
//        cout << "A received: " << cur.i << " " << cur.w << endl;
//        printArr(visited1);
        cur.w += ma1;
        pq1.push(cur);

        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]));
        }

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

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

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;}
};

P DecodeSignal(vector<bool> signal){
    P ans;
    for(int i = 0; i< 11; ++i) ans.i += signal[i] * MASK(i);
    for(int i = 0; i< 20; ++i) ans.w += signal[i+11] * MASK(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;


void SendSignalB(P v){
    bitset<11> u(v.i);
    bitset<9> w(v.w);
    for(int i = 0; i < 11; ++i) SendB(u[i]);
    for(int i = 0; i < 9; ++i) SendB(w[i]);
}


void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    n2 = n; ma2 = 0;
    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]));

    SendSignalB(pq2.top());
}

void ReceiveB(bool x){
    infoB.push_back(x);
    if (infoB.size() == 20){
        P cur = DecodeSignal(infoB);
        infoB.clear();
//        cout << "A received: " << cur.i << " " << cur.w << endl;
//        printArr(visited2);
        cur.w += ma2;
        pq2.push(cur);

        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]));
        }

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

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

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