oj.uz

Submission #482137

# Submission time Handle Problem Language Result Execution time Memory
482137 2021-10-23T11:02:18 Z cheissmart Two Transportations (JOI19_transportations) C++17
62 / 100
 606 ms 48892 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(dist - last_dist == (1 << 9) - 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() { 
        bad1 = bad2 = false;
        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(!bad1 || !bad2)
                    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;
    priority_queue<pi, V<pi>, greater<pi>> pq;
    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(dist - last_dist == (1 << 9) - 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;
                pq.push({d[v], v});
            }
        }
    }

    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;
    pq.push({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) {
                if(pq.size()) pq.pop();
                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 321 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 2 ms 648 KB Output is correct
2 Runtime error 277 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 291 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 223 ms 648 KB Output is correct
2 Correct 239 ms 768 KB Output is correct
3 Correct 247 ms 13308 KB Output is correct
4 Correct 178 ms 712 KB Output is correct
5 Correct 298 ms 10116 KB Output is correct
6 Correct 217 ms 648 KB Output is correct
7 Correct 221 ms 648 KB Output is correct
8 Correct 163 ms 724 KB Output is correct
9 Correct 292 ms 18044 KB Output is correct
10 Correct 308 ms 18180 KB Output is correct
11 Correct 417 ms 35708 KB Output is correct
12 Correct 355 ms 30664 KB Output is correct
13 Correct 225 ms 648 KB Output is correct
14 Correct 2 ms 648 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 648 KB Output is correct
2 Correct 239 ms 768 KB Output is correct
3 Correct 247 ms 13308 KB Output is correct
4 Correct 178 ms 712 KB Output is correct
5 Correct 298 ms 10116 KB Output is correct
6 Correct 217 ms 648 KB Output is correct
7 Correct 221 ms 648 KB Output is correct
8 Correct 163 ms 724 KB Output is correct
9 Correct 292 ms 18044 KB Output is correct
10 Correct 308 ms 18180 KB Output is correct
11 Correct 417 ms 35708 KB Output is correct
12 Correct 355 ms 30664 KB Output is correct
13 Correct 225 ms 648 KB Output is correct
14 Correct 2 ms 648 KB Output is correct
15 Correct 269 ms 648 KB Output is correct
16 Correct 263 ms 648 KB Output is correct
17 Correct 277 ms 716 KB Output is correct
18 Correct 299 ms 10048 KB Output is correct
19 Correct 160 ms 836 KB Output is correct
20 Correct 352 ms 10384 KB Output is correct
21 Correct 208 ms 648 KB Output is correct
22 Correct 259 ms 648 KB Output is correct
23 Correct 374 ms 22148 KB Output is correct
24 Correct 396 ms 22256 KB Output is correct
25 Correct 534 ms 43500 KB Output is correct
26 Correct 423 ms 36364 KB Output is correct
27 Correct 346 ms 756 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 648 KB Output is correct
2 Correct 239 ms 768 KB Output is correct
3 Correct 247 ms 13308 KB Output is correct
4 Correct 178 ms 712 KB Output is correct
5 Correct 298 ms 10116 KB Output is correct
6 Correct 217 ms 648 KB Output is correct
7 Correct 221 ms 648 KB Output is correct
8 Correct 163 ms 724 KB Output is correct
9 Correct 292 ms 18044 KB Output is correct
10 Correct 308 ms 18180 KB Output is correct
11 Correct 417 ms 35708 KB Output is correct
12 Correct 355 ms 30664 KB Output is correct
13 Correct 225 ms 648 KB Output is correct
14 Correct 2 ms 648 KB Output is correct
15 Correct 269 ms 648 KB Output is correct
16 Correct 263 ms 648 KB Output is correct
17 Correct 277 ms 716 KB Output is correct
18 Correct 299 ms 10048 KB Output is correct
19 Correct 160 ms 836 KB Output is correct
20 Correct 352 ms 10384 KB Output is correct
21 Correct 208 ms 648 KB Output is correct
22 Correct 259 ms 648 KB Output is correct
23 Correct 374 ms 22148 KB Output is correct
24 Correct 396 ms 22256 KB Output is correct
25 Correct 534 ms 43500 KB Output is correct
26 Correct 423 ms 36364 KB Output is correct
27 Correct 346 ms 756 KB Output is correct
28 Correct 335 ms 648 KB Output is correct
29 Correct 383 ms 656 KB Output is correct
30 Correct 509 ms 24076 KB Output is correct
31 Correct 318 ms 768 KB Output is correct
32 Correct 366 ms 21124 KB Output is correct
33 Correct 390 ms 728 KB Output is correct
34 Correct 337 ms 904 KB Output is correct
35 Correct 311 ms 904 KB Output is correct
36 Correct 472 ms 24704 KB Output is correct
37 Correct 453 ms 24720 KB Output is correct
38 Correct 606 ms 48892 KB Output is correct
39 Correct 505 ms 44284 KB Output is correct
40 Correct 329 ms 904 KB Output is correct

Subtask #7
0 / 16.0

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