oj.uz

Submission #482139

# Submission time Handle Problem Language Result Execution time Memory
482139 2021-10-23T11:08:06 Z cheissmart Two Transportations (JOI19_transportations) C++17
62 / 100
 620 ms 48876 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 << 11) - 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 << 11) - 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 << 11) - 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 << 11) - 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 << 11) - 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);
        }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 648 KB Output is correct
2 Runtime error 239 ms 324 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 250 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 648 KB Output is correct
2 Correct 232 ms 656 KB Output is correct
3 Correct 307 ms 13368 KB Output is correct
4 Correct 236 ms 648 KB Output is correct
5 Correct 288 ms 10112 KB Output is correct
6 Correct 235 ms 648 KB Output is correct
7 Correct 184 ms 720 KB Output is correct
8 Correct 242 ms 648 KB Output is correct
9 Correct 332 ms 18044 KB Output is correct
10 Correct 345 ms 18192 KB Output is correct
11 Correct 395 ms 35704 KB Output is correct
12 Correct 361 ms 30716 KB Output is correct
13 Correct 221 ms 648 KB Output is correct
14 Correct 2 ms 668 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 648 KB Output is correct
2 Correct 232 ms 656 KB Output is correct
3 Correct 307 ms 13368 KB Output is correct
4 Correct 236 ms 648 KB Output is correct
5 Correct 288 ms 10112 KB Output is correct
6 Correct 235 ms 648 KB Output is correct
7 Correct 184 ms 720 KB Output is correct
8 Correct 242 ms 648 KB Output is correct
9 Correct 332 ms 18044 KB Output is correct
10 Correct 345 ms 18192 KB Output is correct
11 Correct 395 ms 35704 KB Output is correct
12 Correct 361 ms 30716 KB Output is correct
13 Correct 221 ms 648 KB Output is correct
14 Correct 2 ms 668 KB Output is correct
15 Correct 293 ms 648 KB Output is correct
16 Correct 282 ms 720 KB Output is correct
17 Correct 204 ms 648 KB Output is correct
18 Correct 339 ms 10108 KB Output is correct
19 Correct 189 ms 716 KB Output is correct
20 Correct 336 ms 10368 KB Output is correct
21 Correct 295 ms 648 KB Output is correct
22 Correct 268 ms 648 KB Output is correct
23 Correct 366 ms 22140 KB Output is correct
24 Correct 374 ms 22264 KB Output is correct
25 Correct 529 ms 43476 KB Output is correct
26 Correct 431 ms 36368 KB Output is correct
27 Correct 175 ms 776 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 648 KB Output is correct
2 Correct 232 ms 656 KB Output is correct
3 Correct 307 ms 13368 KB Output is correct
4 Correct 236 ms 648 KB Output is correct
5 Correct 288 ms 10112 KB Output is correct
6 Correct 235 ms 648 KB Output is correct
7 Correct 184 ms 720 KB Output is correct
8 Correct 242 ms 648 KB Output is correct
9 Correct 332 ms 18044 KB Output is correct
10 Correct 345 ms 18192 KB Output is correct
11 Correct 395 ms 35704 KB Output is correct
12 Correct 361 ms 30716 KB Output is correct
13 Correct 221 ms 648 KB Output is correct
14 Correct 2 ms 668 KB Output is correct
15 Correct 293 ms 648 KB Output is correct
16 Correct 282 ms 720 KB Output is correct
17 Correct 204 ms 648 KB Output is correct
18 Correct 339 ms 10108 KB Output is correct
19 Correct 189 ms 716 KB Output is correct
20 Correct 336 ms 10368 KB Output is correct
21 Correct 295 ms 648 KB Output is correct
22 Correct 268 ms 648 KB Output is correct
23 Correct 366 ms 22140 KB Output is correct
24 Correct 374 ms 22264 KB Output is correct
25 Correct 529 ms 43476 KB Output is correct
26 Correct 431 ms 36368 KB Output is correct
27 Correct 175 ms 776 KB Output is correct
28 Correct 359 ms 648 KB Output is correct
29 Correct 300 ms 768 KB Output is correct
30 Correct 515 ms 24048 KB Output is correct
31 Correct 338 ms 768 KB Output is correct
32 Correct 483 ms 21108 KB Output is correct
33 Correct 323 ms 732 KB Output is correct
34 Correct 344 ms 884 KB Output is correct
35 Correct 317 ms 904 KB Output is correct
36 Correct 411 ms 24712 KB Output is correct
37 Correct 445 ms 24712 KB Output is correct
38 Correct 620 ms 48876 KB Output is correct
39 Correct 572 ms 44288 KB Output is correct
40 Correct 323 ms 904 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 324 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -