Submission #794809

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
794809	2023-07-26T23:25:20 Z	stasio6	Two Transportations (JOI19_transportations)	C++17	100 / 100	770 ms	48648 KB

Azer
Baijan

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

namespace {

vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
int LD = 0;
bool indx;
int poz, pot, val, gl_N;

void encode(int x, int format) {
    if (x > (1<<format)) x = (1<<format) - 3;
    for (int i = 0; i < format; i++) {
        SendA(x%2);
        x /= 2;
    }
}

void run() {
    pii para;
    while (true) {
        if (pq.empty())
            return;
        para = pq.top();
        if (!odw[para.second])
            break;
        pq.pop();
    }
    int dis = para.first, v = para.second;
    mydist = dis;
    myindx = v;
    encode(dis-LD, 9);
    indx = false; poz = 9, pot = 0, val = 0;
}

void updateEdges(int v) {
    odw[v] = 1;
    for (auto [u, d] : edges[v]) {
        if (dist[u] > dist[v] + d) {
            dist[u] = dist[v] + d;
            pq.push({dist[u], u});
        }
    }
}

}

void ReceiveA(bool bit) {
    val += (1<<pot) * bit;
    pot++;
    poz--;
    if (!poz) {
        if (indx) {
            cerr << "Azer received index " << val << "\n";
            dist[val] = lastdist;
            updateEdges(val);
            run();
        } else {
            cerr << "Azer received distance " << val+LD << "\n";
            cerr << "My " << mydist << "\n";
            lastdist = val + LD;
            if (mydist <= lastdist) {
                LD = mydist;
                cerr << "Time to act! (A)\n";
                updateEdges(myindx);
                encode(myindx, 11);
                run();
            } else {
                LD = lastdist;
                cerr << "Not my turn (A)\n";
                indx = true; poz = 11, pot = 0, val = 0;
            }
        }
    }
}

void InitA(int N, int A, std::vector<signed> U, std::vector<signed> V, std::vector<signed> C) {
    gl_N = N;
    for (int i = 0; i < N; i++) {
        dist[i] = 1000000001;
        pq.push({dist[i], i});
    }
    for (int i = 0; i < A; i++) {
        edges[U[i]].PB({V[i], C[i]});
        edges[V[i]].PB({U[i], C[i]});
    }
    dist[0] = 0;
    pq.push({0, 0});
    run();
}

vector<signed> Answer() {
    vector<signed> ans;
    for (int i = 0; i < gl_N; i++) {
        ans.PB(dist[i]);
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

namespace {

vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
int LD = 0;
bool indx;
int poz, pot, val, gl_N;

void encode(int x, int format) {
    if (x > (1<<format)) x = (1<<format) - 3;
    for (int i = 0; i < format; i++) {
        SendB(x%2);
        x /= 2;
    }
}

void run() {
    pii para;
    while (true) {
        if (pq.empty())
            return;
        para = pq.top();
        if (!odw[para.second])
            break;
        pq.pop();
    }
    int dis = para.first, v = para.second;
    mydist = dis;
    myindx = v;
    encode(dis-LD, 9);
    indx = false; poz = 9, pot = 0, val = 0;
}

void updateEdges(int v) {
    odw[v] = 1;
    for (auto [u, d] : edges[v]) {
        if (dist[u] > dist[v] + d) {
            dist[u] = dist[v] + d;
            pq.push({dist[u], u});
        }
    }
}

}

void ReceiveB(bool bit) {
    val += (1<<pot) * bit;
    pot++;
    poz--;
    if (!poz) {
        if (indx) {
            cerr << "Baihan received index " << val << "\n";
            dist[val] = lastdist;
            updateEdges(val);
            run();
        } else {
            cerr << "Baihan received distance " << val+LD << "\n";
            cerr << "My " << mydist << "\n";
            lastdist = val + LD;
            if (mydist < lastdist) {
                cerr << "Time to act! (B)\n";
                LD = mydist;
                updateEdges(myindx);
                encode(myindx, 11);
                run();
            } else {
                cerr << "Not my turn (B)\n";
                LD = lastdist;
                indx = true; poz = 11, pot = 0, val = 0;
            }
        }
    }
}

void InitB(int N, int B, std::vector<int> U, std::vector<int> V, std::vector<int> D) {
    gl_N = N;
    for (int i = 0; i < N; i++) {
        dist[i] = 1000000001;
        pq.push({dist[i], i});
    }
    for (int i = 0; i < B; i++) {
        edges[U[i]].PB({V[i], D[i]});
        edges[V[i]].PB({U[i], D[i]});
    }
    dist[0] = 0;
    pq.push({0, 0});
    run();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	528 ms	1204 KB	Output is correct
2	Correct	2 ms	656 KB	Output is correct
3	Correct	425 ms	1320 KB	Output is correct
4	Correct	576 ms	10308 KB	Output is correct
5	Correct	33 ms	928 KB	Output is correct
6	Correct	513 ms	2680 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	656 KB	Output is correct
2	Correct	507 ms	1360 KB	Output is correct
3	Correct	381 ms	1240 KB	Output is correct
4	Correct	649 ms	28040 KB	Output is correct
5	Correct	625 ms	24376 KB	Output is correct
6	Correct	102 ms	808 KB	Output is correct
7	Correct	607 ms	24720 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	422 ms	1360 KB	Output is correct
2	Correct	2 ms	604 KB	Output is correct
3	Correct	501 ms	1428 KB	Output is correct
4	Correct	506 ms	1236 KB	Output is correct
5	Correct	387 ms	1140 KB	Output is correct
6	Correct	464 ms	1012 KB	Output is correct
7	Correct	430 ms	1128 KB	Output is correct
8	Correct	450 ms	1216 KB	Output is correct
9	Correct	421 ms	1092 KB	Output is correct
10	Correct	523 ms	1112 KB	Output is correct

Subtask #4
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	908 KB	Output is correct
2	Correct	220 ms	1004 KB	Output is correct
3	Correct	229 ms	13316 KB	Output is correct
4	Correct	201 ms	916 KB	Output is correct
5	Correct	233 ms	10096 KB	Output is correct
6	Correct	230 ms	860 KB	Output is correct
7	Correct	227 ms	1160 KB	Output is correct
8	Correct	262 ms	964 KB	Output is correct
9	Correct	282 ms	18420 KB	Output is correct
10	Correct	290 ms	18400 KB	Output is correct
11	Correct	433 ms	35528 KB	Output is correct
12	Correct	353 ms	30736 KB	Output is correct
13	Correct	230 ms	1200 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	908 KB	Output is correct
2	Correct	220 ms	1004 KB	Output is correct
3	Correct	229 ms	13316 KB	Output is correct
4	Correct	201 ms	916 KB	Output is correct
5	Correct	233 ms	10096 KB	Output is correct
6	Correct	230 ms	860 KB	Output is correct
7	Correct	227 ms	1160 KB	Output is correct
8	Correct	262 ms	964 KB	Output is correct
9	Correct	282 ms	18420 KB	Output is correct
10	Correct	290 ms	18400 KB	Output is correct
11	Correct	433 ms	35528 KB	Output is correct
12	Correct	353 ms	30736 KB	Output is correct
13	Correct	230 ms	1200 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	271 ms	908 KB	Output is correct
16	Correct	259 ms	868 KB	Output is correct
17	Correct	267 ms	1128 KB	Output is correct
18	Correct	334 ms	10124 KB	Output is correct
19	Correct	227 ms	1084 KB	Output is correct
20	Correct	308 ms	10324 KB	Output is correct
21	Correct	263 ms	1284 KB	Output is correct
22	Correct	286 ms	968 KB	Output is correct
23	Correct	362 ms	22416 KB	Output is correct
24	Correct	351 ms	22304 KB	Output is correct
25	Correct	554 ms	43632 KB	Output is correct
26	Correct	472 ms	36636 KB	Output is correct
27	Correct	263 ms	1496 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	908 KB	Output is correct
2	Correct	220 ms	1004 KB	Output is correct
3	Correct	229 ms	13316 KB	Output is correct
4	Correct	201 ms	916 KB	Output is correct
5	Correct	233 ms	10096 KB	Output is correct
6	Correct	230 ms	860 KB	Output is correct
7	Correct	227 ms	1160 KB	Output is correct
8	Correct	262 ms	964 KB	Output is correct
9	Correct	282 ms	18420 KB	Output is correct
10	Correct	290 ms	18400 KB	Output is correct
11	Correct	433 ms	35528 KB	Output is correct
12	Correct	353 ms	30736 KB	Output is correct
13	Correct	230 ms	1200 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	271 ms	908 KB	Output is correct
16	Correct	259 ms	868 KB	Output is correct
17	Correct	267 ms	1128 KB	Output is correct
18	Correct	334 ms	10124 KB	Output is correct
19	Correct	227 ms	1084 KB	Output is correct
20	Correct	308 ms	10324 KB	Output is correct
21	Correct	263 ms	1284 KB	Output is correct
22	Correct	286 ms	968 KB	Output is correct
23	Correct	362 ms	22416 KB	Output is correct
24	Correct	351 ms	22304 KB	Output is correct
25	Correct	554 ms	43632 KB	Output is correct
26	Correct	472 ms	36636 KB	Output is correct
27	Correct	263 ms	1496 KB	Output is correct
28	Correct	377 ms	1140 KB	Output is correct
29	Correct	325 ms	1004 KB	Output is correct
30	Correct	510 ms	24008 KB	Output is correct
31	Correct	283 ms	1004 KB	Output is correct
32	Correct	443 ms	21044 KB	Output is correct
33	Correct	303 ms	928 KB	Output is correct
34	Correct	403 ms	1132 KB	Output is correct
35	Correct	324 ms	1196 KB	Output is correct
36	Correct	437 ms	24948 KB	Output is correct
37	Correct	458 ms	25008 KB	Output is correct
38	Correct	608 ms	48648 KB	Output is correct
39	Correct	510 ms	44132 KB	Output is correct
40	Correct	381 ms	1216 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	528 ms	1204 KB	Output is correct
2	Correct	2 ms	656 KB	Output is correct
3	Correct	425 ms	1320 KB	Output is correct
4	Correct	576 ms	10308 KB	Output is correct
5	Correct	33 ms	928 KB	Output is correct
6	Correct	513 ms	2680 KB	Output is correct
7	Correct	2 ms	656 KB	Output is correct
8	Correct	507 ms	1360 KB	Output is correct
9	Correct	381 ms	1240 KB	Output is correct
10	Correct	649 ms	28040 KB	Output is correct
11	Correct	625 ms	24376 KB	Output is correct
12	Correct	102 ms	808 KB	Output is correct
13	Correct	607 ms	24720 KB	Output is correct
14	Correct	422 ms	1360 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	501 ms	1428 KB	Output is correct
17	Correct	506 ms	1236 KB	Output is correct
18	Correct	387 ms	1140 KB	Output is correct
19	Correct	464 ms	1012 KB	Output is correct
20	Correct	430 ms	1128 KB	Output is correct
21	Correct	450 ms	1216 KB	Output is correct
22	Correct	421 ms	1092 KB	Output is correct
23	Correct	523 ms	1112 KB	Output is correct
24	Correct	165 ms	908 KB	Output is correct
25	Correct	220 ms	1004 KB	Output is correct
26	Correct	229 ms	13316 KB	Output is correct
27	Correct	201 ms	916 KB	Output is correct
28	Correct	233 ms	10096 KB	Output is correct
29	Correct	230 ms	860 KB	Output is correct
30	Correct	227 ms	1160 KB	Output is correct
31	Correct	262 ms	964 KB	Output is correct
32	Correct	282 ms	18420 KB	Output is correct
33	Correct	290 ms	18400 KB	Output is correct
34	Correct	433 ms	35528 KB	Output is correct
35	Correct	353 ms	30736 KB	Output is correct
36	Correct	230 ms	1200 KB	Output is correct
37	Correct	2 ms	656 KB	Output is correct
38	Correct	271 ms	908 KB	Output is correct
39	Correct	259 ms	868 KB	Output is correct
40	Correct	267 ms	1128 KB	Output is correct
41	Correct	334 ms	10124 KB	Output is correct
42	Correct	227 ms	1084 KB	Output is correct
43	Correct	308 ms	10324 KB	Output is correct
44	Correct	263 ms	1284 KB	Output is correct
45	Correct	286 ms	968 KB	Output is correct
46	Correct	362 ms	22416 KB	Output is correct
47	Correct	351 ms	22304 KB	Output is correct
48	Correct	554 ms	43632 KB	Output is correct
49	Correct	472 ms	36636 KB	Output is correct
50	Correct	263 ms	1496 KB	Output is correct
51	Correct	377 ms	1140 KB	Output is correct
52	Correct	325 ms	1004 KB	Output is correct
53	Correct	510 ms	24008 KB	Output is correct
54	Correct	283 ms	1004 KB	Output is correct
55	Correct	443 ms	21044 KB	Output is correct
56	Correct	303 ms	928 KB	Output is correct
57	Correct	403 ms	1132 KB	Output is correct
58	Correct	324 ms	1196 KB	Output is correct
59	Correct	437 ms	24948 KB	Output is correct
60	Correct	458 ms	25008 KB	Output is correct
61	Correct	608 ms	48648 KB	Output is correct
62	Correct	510 ms	44132 KB	Output is correct
63	Correct	381 ms	1216 KB	Output is correct
64	Correct	447 ms	1360 KB	Output is correct
65	Correct	529 ms	26756 KB	Output is correct
66	Correct	647 ms	23468 KB	Output is correct
67	Correct	412 ms	1468 KB	Output is correct
68	Correct	524 ms	1340 KB	Output is correct
69	Correct	770 ms	47628 KB	Output is correct
70	Correct	639 ms	39552 KB	Output is correct
71	Correct	551 ms	5004 KB	Output is correct
72	Correct	391 ms	1580 KB	Output is correct

Submission #794809

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 8.0 / 8.0

Subtask #4 38.0 / 38.0

Subtask #5 14.0 / 14.0

Subtask #6 10.0 / 10.0

Subtask #7 16.0 / 16.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
8.0 / 8.0

Subtask #4
38.0 / 38.0

Subtask #5
14.0 / 14.0

Subtask #6
10.0 / 10.0

Subtask #7
16.0 / 16.0