제출 #1307563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307563		Zero_OP	Two Transportations (JOI19_transportations)	C++20	100 / 100	329 ms	51824 KiB

Azer

#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

namespace Azer{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
    return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
    return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

const int MAX = 2e3 + 5;

int N, M, T, c, LOG_N, LOG_500, stateA, stateB, minA, num, remainBits, type, dist[MAX], vis[MAX];
vpi adj[MAX];

/*

Estimation and Notes
- max LOG_N = 11 Bits
- LOG_500 = 9 Bits
- type = 1 : Delta
- type = 2 : index


*/

int findCandidate(){
    int res = -1;
    F0R(i, N) if(!vis[i]){
        if(res == -1 || dist[i] < dist[res]){
          res = i;
        }
    }
    return res;
}

void sendDist(int d){
    for(int i = LOG_500; i >= 0; --i){
        SendA(d >> i & 1);
    }
    num = 0;
    remainBits = LOG_500 + 1;
    type = 1;
}

void sendIndex(int id){
    for(int i = LOG_N; i >= 0; --i){
        SendA(id >> i & 1);
    }
    num = 0;
    remainBits = LOG_N + 1;
    type = 2;
}

void relax(int u){
    // cerr << "Azer relax " << u << " | " << dist[u] << '\n';
    stateA = stateB = dist[u];
    vis[u] = 1;
    for(auto [v, w] : adj[u]){
        minimize(dist[v], dist[u] + w);
    }

    ++T;
    if(T == N) return;

    c = findCandidate();
    int gap = min(503, dist[c] - dist[u]); //instead of storing the whole dist, we just need to store the \Delta
    minA = dist[c];
    // cerr << "Azer send " << gap << ", candidate = " << c << '\n';
    sendDist(gap);
}

}  // namespace

using namespace Azer;

void InitA(int N, int M, vector<int> U, vector<int> V, vector<int> C) {
    ::N = N;
    F0R(i, M){
        int u = U[i], v = V[i], w = C[i];
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }

    memset(dist, 0x3f, sizeof(dist));
    LOG_N = 31 - __builtin_clz(N - 1);
    LOG_500 = 31 - __builtin_clz(500);

    dist[0] = 0;
    relax(0);
}

void ReceiveA(bool x) {
    num = 2 * num + x;
    --remainBits;
    assert(remainBits >= 0);
    if(remainBits == 0){
        // cerr << "Azer : " << "num = " << num << ", type = " << type << '\n';
        if(type == 1){
            stateB += num;
            if(minA <= stateB){
                stateB = minA;
                sendIndex(c);
                relax(c);
            } else{ //start receive the index
                num = 0;
                remainBits = LOG_N + 1;
                type = 2;
            }
        } else{
            assert(minA > stateB);
            dist[num] = stateB;
            relax(num);
        }
        num = 0;
    } 
}

std::vector<int> Answer() {
    vi ans(dist, dist + N);
    return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

namespace Baijan{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
    return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
    return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

const int MAX = 2e3 + 5;

int N, M, T, c, LOG_N, LOG_500, stateA, stateB, num, minB, remainBits, type, dist[MAX], vis[MAX];
vpi adj[MAX];

/*

Estimation and Notes
- max LOG_N = 11 Bits
- LOG_500 = 9 Bits
- type = 1 : Delta
- type = 2 : index


*/

int findCandidate(){
    int res = -1;
    F0R(i, N) if(!vis[i]){
        if(res == -1 || dist[i] < dist[res]){
          res = i;
        }
    }
    return res;
}

void sendDist(int d){
    for(int i = LOG_500; i >= 0; --i){
        SendB(d >> i & 1);
    }
    num = 0;
    remainBits = LOG_500 + 1;
    type = 1;
}

void sendIndex(int id){
    for(int i = LOG_N; i >= 0; --i){
        SendB(id >> i & 1);
    }
    num = 0;
    remainBits = LOG_N + 1;
    type = 2;
}

void relax(int u){
    // cerr << "Baijan relax " << u << " | " << dist[u] << '\n';
    stateA = stateB = dist[u];
    vis[u] = 1;
    for(auto [v, w] : adj[u]){
        minimize(dist[v], dist[u] + w);
    }

    ++T;
    if(T == N) return;

    c = findCandidate();
    int gap = min(503, dist[c] - dist[u]); //instead of storing the whole dist, we just need to store the \Delta

    minB = dist[c];
    // cerr << "Baijan send " << gap << ", candidate = " << c << '\n';
    sendDist(gap);
}

}  // namespace

using namespace Baijan;

void InitB(int N, int M, vector<int> U, vector<int> V, vector<int> C) {
    ::N = N;

    F0R(i, M){
        int u = U[i], v = V[i], w = C[i];
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }

    memset(dist, 0x3f, sizeof(dist));
    LOG_N = 31 - __builtin_clz(N - 1);
    LOG_500 = 31 - __builtin_clz(500);

    dist[0] = 0;
    relax(0);
}

void ReceiveB(bool x) {
    num = 2 * num + x;
    --remainBits;
    assert(remainBits >= 0);
    if(remainBits == 0){
        // cerr << "Baijan : " << "num = " << num << ", type = " << type << '\n';
        if(type == 1){
            stateA += num;
            if(minB < stateA){
                stateA = minB;
                sendIndex(c);
                relax(c);
            } else{ //start receive the index
                num = 0;
                remainBits = LOG_N + 1;
                type = 2;
            }
        } else{
            assert(minB >= stateA);
            dist[num] = stateA;
            relax(num);
        }
        num = 0;
    } 
}

• 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