Submission #259351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259351	2020-08-07T16:22:01 Z	keko37	Two Transportations (JOI19_transportations)	C++14	100 / 100	2170 ms	85544 KB

Azer
Baijan

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

using namespace std;

typedef pair <int, int> pi;

const int MAXN = 2005;

int n, m, mx, ans, ex, tip, mn, ind, ost, role;
vector <pi> v[MAXN];
int bio[MAXN], dist[MAXN];

//void SendA (bool x) {}

void SendNum (int val, int br) {
    for (int i = br - 1; i >= 0; i--) {
        SendA((bool) (val & (1 << i)));
    }
}

void update (int x, int d) {
    bio[x] = 1; dist[x] = d;
    mx = max(mx, dist[x]);
    for (auto par : v[x]) {
        int sus = par.first, w = par.second;
        if (bio[sus] == 0 && dist[x] + w < dist[sus]) dist[sus] = dist[x] + w;
    }
}

void solve () {
    if (ost == 0) return;
    if (tip == 0) {
        role = rand() % 2;
        SendNum(role, 1);
        tip = 1; solve();
    } else if (role == 0) {
        if (tip == 1) {
            mn = 501, ind = -1;
            for (int j = 1; j <= n; j++) {
                if (bio[j] == 0 && dist[j] - mx < mn) {
                    mn = dist[j] - mx;
                    ind = j;
                }
            }

            SendNum(mn, 9);
            ans = 0; ex = 1;
        } else if (tip == 2) {
            if (ans == 0) {
                SendNum(ind, 11);
                tip = 5;
                solve();
            } else {
                ans = 0; ex = 9;
            }
        } else if (tip == 3) {
            mn = ans;
            ans = 0; ex = 11;
        } else if (tip == 4) {
            ind = ans;
            tip = 5;
            solve();
        } else if (tip == 5) {
            update(ind, mx + mn);
            tip = 0;
            ost--;
            solve();
        }
    } else {
        if (tip == 1) {
            mn = 501, ind = -1;
            for (int j = 1; j <= n; j++) {
                if (bio[j] == 0 && dist[j] - mx < mn) {
                    mn = dist[j] - mx;
                    ind = j;
                }
            }

            ans = 0; ex = 9;
        } else if (tip == 2) {
            if (mn < ans) {
                SendNum(1, 1);
                SendNum(mn, 9);
                SendNum(ind, 11);
                tip = 4;
                solve();
            } else {
                SendNum(0, 1);
                mn = ans;
                ans = 0; ex = 11;
            }
        } else if (tip == 3) {
            ind = ans;
            tip = 4;
            solve();
        } else if (tip == 4) {
            update(ind, mx + mn);
            tip = 0;
            ost--;
            solve();
        }
    }
}

void ReceiveA (bool x) {
    ans *= 2;
    if (x) ans++;
    ex--;
    if (ex == 0) {
        tip++;
        solve();
    }
}

std::vector<int> Answer () {
    vector <int> res(n);
    for (int i = 0; i < n; i++) res[i] = dist[i];
    return res;
}

void InitA (int N, int A, std::vector <int> U, std::vector <int> V, std::vector <int> C) {
    n = N; m = A;
    for (int i = 0; i < m; i++) {
        v[U[i]].push_back({V[i], C[i]});
        v[V[i]].push_back({U[i], C[i]});
    }
    for (int i = 1; i <= n; i++) dist[i] = 1e9;
    update(0, 0);
    ost = n-1;
    solve();
}

/*int main () {
    return 0;
}*/

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

using namespace std;

typedef pair <int, int> pi;

const int MAXN = 2005;

int n, m, mx, ans, ex, tip, mn, ind, ost, role;
vector <pi> v[MAXN];
int bio[MAXN], dist[MAXN];

//void SendB (bool x) {}

void SendNum (int val, int br) {
    for (int i = br - 1; i >= 0; i--) {
        SendB((bool) (val & (1 << i)));
    }
}

void update (int x, int d) {
    bio[x] = 1; dist[x] = d;
    mx = max(mx, dist[x]);
    for (auto par : v[x]) {
        int sus = par.first, w = par.second;
        if (bio[sus] == 0 && dist[x] + w < dist[sus]) dist[sus] = dist[x] + w;
    }
}

void solve () {
    if (ost == 0) return;
    if (tip == 0) {
        ans = 0; ex = 1;
    } else if (tip == 1) {
        role = !ans;
        tip++; solve();
    } else if (role == 0) {
        if (tip == 2) {
            mn = 501, ind = -1;
            for (int j = 1; j <= n; j++) {
                if (bio[j] == 0 && dist[j] - mx < mn) {
                    mn = dist[j] - mx;
                    ind = j;
                }
            }

            SendNum(mn, 9);
            ans = 0; ex = 1;
        } else if (tip == 3) {
            if (ans == 0) {
                SendNum(ind, 11);
                tip = 6;
                solve();
            } else {
                ans = 0; ex = 9;
            }
        } else if (tip == 4) {
            mn = ans;
            ans = 0; ex = 11;
        } else if (tip == 5) {
            ind = ans;
            tip = 6;
            solve();
        } else if (tip == 6) {
            update(ind, mx + mn);
            tip = 0;
            ost--;
            solve();
        }
    } else {
        if (tip == 2) {
            mn = 501, ind = -1;
            for (int j = 1; j <= n; j++) {
                if (bio[j] == 0 && dist[j] - mx < mn) {
                    mn = dist[j] - mx;
                    ind = j;
                }
            }

            ans = 0; ex = 9;
        } else if (tip == 3) {
            if (mn < ans) {
                SendNum(1, 1);
                SendNum(mn, 9);
                SendNum(ind, 11);
                tip = 5;
                solve();
            } else {
                SendNum(0, 1);
                mn = ans;
                ans = 0; ex = 11;
            }
        } else if (tip == 4) {
            ind = ans;
            tip = 5;
            solve();
        } else if (tip == 5) {
            update(ind, mx + mn);
            tip = 0;
            ost--;
            solve();
        }
    }
}

void ReceiveB (bool x) {
    ans *= 2;
    if (x) ans++;
    ex--;
    if (ex == 0) {
        tip++;
        solve();
    }
}

void InitB (int N, int B, std::vector <int> U, std::vector <int> V, std::vector <int> C) {
    n = N; m = B;
    for (int i = 0; i < m; i++) {
        v[U[i]].push_back({V[i], C[i]});
        v[V[i]].push_back({U[i], C[i]});
    }
    for (int i = 1; i <= n; i++) dist[i] = 1e9;
    update(0, 0);
    ost = n-1;
    solve();
}

/*int main () {
    return 0;
}*/

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1048 ms	2016 KB	Output is correct
2	Correct	2 ms	1280 KB	Output is correct
3	Correct	850 ms	1560 KB	Output is correct
4	Correct	1248 ms	20192 KB	Output is correct
5	Correct	50 ms	1608 KB	Output is correct
6	Correct	1484 ms	4576 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1280 KB	Output is correct
2	Correct	1094 ms	1904 KB	Output is correct
3	Correct	1110 ms	1536 KB	Output is correct
4	Correct	1504 ms	55264 KB	Output is correct
5	Correct	1348 ms	48368 KB	Output is correct
6	Correct	184 ms	1536 KB	Output is correct
7	Correct	1124 ms	48392 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1298 ms	1592 KB	Output is correct
2	Correct	2 ms	1536 KB	Output is correct
3	Correct	906 ms	1792 KB	Output is correct
4	Correct	1308 ms	1680 KB	Output is correct
5	Correct	1502 ms	1632 KB	Output is correct
6	Correct	1054 ms	1536 KB	Output is correct
7	Correct	880 ms	1616 KB	Output is correct
8	Correct	876 ms	1840 KB	Output is correct
9	Correct	1032 ms	1280 KB	Output is correct
10	Correct	904 ms	1856 KB	Output is correct

Subtask #4
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	482 ms	1536 KB	Output is correct
2	Correct	512 ms	1504 KB	Output is correct
3	Correct	580 ms	24056 KB	Output is correct
4	Correct	664 ms	1536 KB	Output is correct
5	Correct	656 ms	17376 KB	Output is correct
6	Correct	586 ms	1536 KB	Output is correct
7	Correct	570 ms	1536 KB	Output is correct
8	Correct	420 ms	1536 KB	Output is correct
9	Correct	788 ms	36088 KB	Output is correct
10	Correct	1062 ms	35864 KB	Output is correct
11	Correct	1120 ms	61360 KB	Output is correct
12	Correct	840 ms	53848 KB	Output is correct
13	Correct	426 ms	1792 KB	Output is correct
14	Correct	4 ms	1560 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	482 ms	1536 KB	Output is correct
2	Correct	512 ms	1504 KB	Output is correct
3	Correct	580 ms	24056 KB	Output is correct
4	Correct	664 ms	1536 KB	Output is correct
5	Correct	656 ms	17376 KB	Output is correct
6	Correct	586 ms	1536 KB	Output is correct
7	Correct	570 ms	1536 KB	Output is correct
8	Correct	420 ms	1536 KB	Output is correct
9	Correct	788 ms	36088 KB	Output is correct
10	Correct	1062 ms	35864 KB	Output is correct
11	Correct	1120 ms	61360 KB	Output is correct
12	Correct	840 ms	53848 KB	Output is correct
13	Correct	426 ms	1792 KB	Output is correct
14	Correct	4 ms	1560 KB	Output is correct
15	Correct	672 ms	1536 KB	Output is correct
16	Correct	590 ms	1536 KB	Output is correct
17	Correct	528 ms	1536 KB	Output is correct
18	Correct	580 ms	17720 KB	Output is correct
19	Correct	620 ms	1536 KB	Output is correct
20	Correct	738 ms	18000 KB	Output is correct
21	Correct	620 ms	1536 KB	Output is correct
22	Correct	682 ms	1792 KB	Output is correct
23	Correct	1216 ms	44000 KB	Output is correct
24	Correct	1126 ms	44000 KB	Output is correct
25	Correct	1418 ms	75256 KB	Output is correct
26	Correct	1056 ms	64448 KB	Output is correct
27	Correct	690 ms	2048 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	482 ms	1536 KB	Output is correct
2	Correct	512 ms	1504 KB	Output is correct
3	Correct	580 ms	24056 KB	Output is correct
4	Correct	664 ms	1536 KB	Output is correct
5	Correct	656 ms	17376 KB	Output is correct
6	Correct	586 ms	1536 KB	Output is correct
7	Correct	570 ms	1536 KB	Output is correct
8	Correct	420 ms	1536 KB	Output is correct
9	Correct	788 ms	36088 KB	Output is correct
10	Correct	1062 ms	35864 KB	Output is correct
11	Correct	1120 ms	61360 KB	Output is correct
12	Correct	840 ms	53848 KB	Output is correct
13	Correct	426 ms	1792 KB	Output is correct
14	Correct	4 ms	1560 KB	Output is correct
15	Correct	672 ms	1536 KB	Output is correct
16	Correct	590 ms	1536 KB	Output is correct
17	Correct	528 ms	1536 KB	Output is correct
18	Correct	580 ms	17720 KB	Output is correct
19	Correct	620 ms	1536 KB	Output is correct
20	Correct	738 ms	18000 KB	Output is correct
21	Correct	620 ms	1536 KB	Output is correct
22	Correct	682 ms	1792 KB	Output is correct
23	Correct	1216 ms	44000 KB	Output is correct
24	Correct	1126 ms	44000 KB	Output is correct
25	Correct	1418 ms	75256 KB	Output is correct
26	Correct	1056 ms	64448 KB	Output is correct
27	Correct	690 ms	2048 KB	Output is correct
28	Correct	668 ms	1536 KB	Output is correct
29	Correct	1048 ms	1792 KB	Output is correct
30	Correct	1252 ms	42136 KB	Output is correct
31	Correct	938 ms	1536 KB	Output is correct
32	Correct	894 ms	37416 KB	Output is correct
33	Correct	974 ms	1720 KB	Output is correct
34	Correct	954 ms	1792 KB	Output is correct
35	Correct	848 ms	1792 KB	Output is correct
36	Correct	1100 ms	49120 KB	Output is correct
37	Correct	1094 ms	49408 KB	Output is correct
38	Correct	1604 ms	85544 KB	Output is correct
39	Correct	1472 ms	78640 KB	Output is correct
40	Correct	846 ms	2096 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1048 ms	2016 KB	Output is correct
2	Correct	2 ms	1280 KB	Output is correct
3	Correct	850 ms	1560 KB	Output is correct
4	Correct	1248 ms	20192 KB	Output is correct
5	Correct	50 ms	1608 KB	Output is correct
6	Correct	1484 ms	4576 KB	Output is correct
7	Correct	2 ms	1280 KB	Output is correct
8	Correct	1094 ms	1904 KB	Output is correct
9	Correct	1110 ms	1536 KB	Output is correct
10	Correct	1504 ms	55264 KB	Output is correct
11	Correct	1348 ms	48368 KB	Output is correct
12	Correct	184 ms	1536 KB	Output is correct
13	Correct	1124 ms	48392 KB	Output is correct
14	Correct	1298 ms	1592 KB	Output is correct
15	Correct	2 ms	1536 KB	Output is correct
16	Correct	906 ms	1792 KB	Output is correct
17	Correct	1308 ms	1680 KB	Output is correct
18	Correct	1502 ms	1632 KB	Output is correct
19	Correct	1054 ms	1536 KB	Output is correct
20	Correct	880 ms	1616 KB	Output is correct
21	Correct	876 ms	1840 KB	Output is correct
22	Correct	1032 ms	1280 KB	Output is correct
23	Correct	904 ms	1856 KB	Output is correct
24	Correct	482 ms	1536 KB	Output is correct
25	Correct	512 ms	1504 KB	Output is correct
26	Correct	580 ms	24056 KB	Output is correct
27	Correct	664 ms	1536 KB	Output is correct
28	Correct	656 ms	17376 KB	Output is correct
29	Correct	586 ms	1536 KB	Output is correct
30	Correct	570 ms	1536 KB	Output is correct
31	Correct	420 ms	1536 KB	Output is correct
32	Correct	788 ms	36088 KB	Output is correct
33	Correct	1062 ms	35864 KB	Output is correct
34	Correct	1120 ms	61360 KB	Output is correct
35	Correct	840 ms	53848 KB	Output is correct
36	Correct	426 ms	1792 KB	Output is correct
37	Correct	4 ms	1560 KB	Output is correct
38	Correct	672 ms	1536 KB	Output is correct
39	Correct	590 ms	1536 KB	Output is correct
40	Correct	528 ms	1536 KB	Output is correct
41	Correct	580 ms	17720 KB	Output is correct
42	Correct	620 ms	1536 KB	Output is correct
43	Correct	738 ms	18000 KB	Output is correct
44	Correct	620 ms	1536 KB	Output is correct
45	Correct	682 ms	1792 KB	Output is correct
46	Correct	1216 ms	44000 KB	Output is correct
47	Correct	1126 ms	44000 KB	Output is correct
48	Correct	1418 ms	75256 KB	Output is correct
49	Correct	1056 ms	64448 KB	Output is correct
50	Correct	690 ms	2048 KB	Output is correct
51	Correct	668 ms	1536 KB	Output is correct
52	Correct	1048 ms	1792 KB	Output is correct
53	Correct	1252 ms	42136 KB	Output is correct
54	Correct	938 ms	1536 KB	Output is correct
55	Correct	894 ms	37416 KB	Output is correct
56	Correct	974 ms	1720 KB	Output is correct
57	Correct	954 ms	1792 KB	Output is correct
58	Correct	848 ms	1792 KB	Output is correct
59	Correct	1100 ms	49120 KB	Output is correct
60	Correct	1094 ms	49408 KB	Output is correct
61	Correct	1604 ms	85544 KB	Output is correct
62	Correct	1472 ms	78640 KB	Output is correct
63	Correct	846 ms	2096 KB	Output is correct
64	Correct	1252 ms	2048 KB	Output is correct
65	Correct	1332 ms	47328 KB	Output is correct
66	Correct	1460 ms	40856 KB	Output is correct
67	Correct	1068 ms	2424 KB	Output is correct
68	Correct	1076 ms	1920 KB	Output is correct
69	Correct	2170 ms	83440 KB	Output is correct
70	Correct	1608 ms	68296 KB	Output is correct
71	Correct	1282 ms	9152 KB	Output is correct
72	Correct	884 ms	2152 KB	Output is correct

Submission #259351

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