답안 #482138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482138 2021-10-23T11:06:16 Z cheissmart Two Transportations (JOI19_transportations) C++17
0 / 100
288 ms 324 KB
#include "Azer.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;


const int INF = 1e9 + 7, N = 2005;

namespace {
    V<pi> G[N];
    int d[N], vis[N];
    int n;
    int state, last_dist;
    int u, dist, code, cnt;
    bool bad1, bad2;
    // state
    // 0: to sent
    // 1: waiting B cost
    // 2: watting B for who

    void send_cost(int cost) {
        for(int i = 8; i >= 0; i--)
            SendA(cost >> i & 1);
    }
    void send_who(int who) {
        for(int i = 10; i >= 0; i--)
            SendA(who >> i & 1);
    }

    void upd(int dist, int u) {
        if(u == -1)
            return;
        assert(!vis[u]);
        d[u] = dist;
        vis[u] = 1;
        last_dist = dist;
        for(auto [v, w]:G[u]) {
            if(d[u] + w < d[v]) {
                d[v] = d[u] + w;
            }
        }
    }

    void start() { 
        assert(state == 0);
        dist = last_dist + (1 << 9) - 1, u = -1;
        for(int i = 0; i < n; i++) if(!vis[i]) {
            if(d[i] < dist) {
                dist = d[i];
                u = i;
            }
        }
        if(u == -1)
            bad1 = true;
        send_cost(dist - last_dist);
        state = 1;
    }

}  // namespace

void InitA(int _n, int A, vi u, vi v, vi c) {
    n = _n;
    for(int i = 0; i < A; i++) {
        G[u[i]].EB(v[i], c[i]);
        G[v[i]].EB(u[i], c[i]);
    }
    memset(d, 0x3f, sizeof(d[0]) * n);
    memset(vis, 0, sizeof(vis[0]) * n);
    d[0] = 0;

    state = 0;
    last_dist = 0;
    code = 0;
    cnt = 0;
    start();
}

void ReceiveA(bool x) {
    if(state == 1) {
        code = code * 2 + x;
        cnt++;
        if(cnt == 9) {
            if(code == (1 << 9) - 1)
                bad2 = true;
            if(last_dist + code < dist) {
                dist = last_dist + code;
                state = 2;
                code = 0;
                cnt = 0;
            } else {
                send_who(u);
                upd(dist, u);
                state = 0;
                code = 0;
                cnt = 0;
                if(u != -1)
                    start();
            }
        }
    } else if(state == 2) {
        code = code * 2 + x;
        cnt++;
        if(cnt == 11) {
            u = code;
            upd(dist, u);
            state = 0;
            code = 0;
            cnt = 0;
            start();
        }
     } else throw;
}

vi Answer() {
    vi ans(n);
    for(int i = 0; i < n; i++) {
        assert(vis[i]);
        ans[i] = d[i];
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2005;
namespace {
    V<pi> G[N];
    int d[N], vis[N];
    int n;
    int state, last_dist;
    int u, dist, code, cnt;
    // state
    // 0: wait A
    // 1: 

    void send_cost(int cost) {
        for(int i = 8; i >= 0; i--)
            SendB(cost >> i & 1);
    }
    void send_who(int who) {
        for(int i = 10; i >= 0; i--)
            SendB(who >> i & 1);
    }

    void upd(int dist, int u) {
        if(u == -1)
            return;
        d[u] = dist;
        vis[u] = 1;
        last_dist = dist;
        for(auto [v, w]:G[u]) {
            if(d[u] + w < d[v]) {
                d[v] = d[u] + w;
            }
        }
    }

    void start() { 
        dist = last_dist + (1 << 9) - 1, u = -1;
        for(int i = 0; i < n; i++) if(!vis[i]) {
            if(d[i] < dist) {
                dist = d[i];
                u = i;
            }
        }
    }
}  // namespace


void InitB(int _n, int A, vi u, vi v, vi c) {
    n = _n;
    for(int i = 0; i < A; i++) {
        G[u[i]].EB(v[i], c[i]);
        G[v[i]].EB(u[i], c[i]);
    }
    memset(d, 0x3f, sizeof(d[0]) * n);
    memset(vis, 0, sizeof(vis[0]) * n);
    d[0] = 0;

    state = 0;
    last_dist = 0;
    code = 0;
    cnt = 0;
}

void ReceiveB(bool x) {
    if(state == 0) {
        code = code * 2 + x;
        cnt++;
        if(cnt == 9) {
            start();
            if(last_dist + code > dist) {
                int tt = dist - last_dist;
                cnt = 0;
                code = 0;
                state = 0;
                upd(dist, u);
                send_cost(tt);
                send_who(u);
            } else {
                int tt = dist - last_dist;
                dist = last_dist + code;
                cnt = 0;
                code = 0;
                state = 1;
                send_cost(tt);
            }
        }
    } else if(state == 1) {
        code = code * 2 + x;
        cnt++;
        if(cnt == 11) {
            u = code;
            cnt = 0;
            code = 0;
            state = 0;
            upd(dist, u);
        }
    }
}

# 결과 실행 시간 메모리 Grader output
1 Runtime error 288 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 215 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 57 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 57 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 57 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 288 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -