답안 #748618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748618	2023-05-26T15:17:48 Z	piOOE	Two Transportations (JOI19_transportations)	C++17	100 / 100	734 ms	48896 KB

Azer
Baijan

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

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58001;
    constexpr int inf = 1e9 + 7;

    int N, A, Q = 0, S = 0, Last = 0, usedCnt = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }

    void ckmin(int v, int d) {
        if (dist[v] > d) {
            st.erase({dist[v], v});
            st.emplace(dist[v] = d, v);
//            upd(v);
        }
    }
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    ::N = N, ::A = A;

    for (int i = 0; i < A; ++i) {
        adj[U[i]].emplace_back(V[i], C[i]);
        adj[V[i]].emplace_back(U[i], C[i]);
    }

    fill(dist, dist + N, inf);

    ckmin(0, 0);

    for (int i = 0; i < 9; ++i) {
        SendA(0);
    }
}

void ReceiveA(bool x) {
    b[Q++] = x;

    if (Q - Last == 9) {
        int nd = 0;

        for (int i = 0; i < 9; ++i) {
            nd |= b[Last + i] << i;
        }

        if (nd > 500) {
            auto [d, v] = *st.begin();
            st.erase(st.begin());

            upd(v);
            assert(!used[v]);
            used[v] = true;
            usedCnt += 1;
            S = d;

            for (int i = 0; i < 11; ++i) {
                SendA(v >> i & 1);
            }

            Last = Q;
        }
    } else if (Q - Last == 9 + 11) {
        int nd = 0, v = 0;

        for (int i = 0; i < 9; ++i) {
            nd |= b[Last + i] << i;
        }
        for (int i = 0; i < 11; ++i) {
            v |= b[Last + i + 9] << i;
        }

        assert(!used[v]);
        used[v] = true;
        usedCnt += 1;
        ckmin(v, S + nd);
        upd(v);
        st.erase({dist[v], v});
        S += nd;
        Last = Q;
    }

    if (Q == Last) {
        if (usedCnt == N) {
            return;
        } else if (st.empty()) {
            for (int i = 0; i < 9; ++i) {
                SendA(1);
            }
            return;
        }

        int d = st.begin()->first - S;

        for (int i = 0; i < 9; ++i) {
            SendA(d >> i & 1);
        }
    }
}

std::vector<int> Answer() {
    std::vector<int> ans(N);
    for (int k = 0; k < N; ++k) {
        ans[k] = dist[k];
    }
    return ans;
}

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

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58000;
    constexpr int inf = 1e9 + 7;

    int N, B, Q = 0, S = 0, Last = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }

    void ckmin(int v, int d) {
        if (dist[v] > d) {
            st.erase({dist[v], v});
            st.emplace(dist[v] = d, v);
//            upd(v);
        }
    }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N, ::B = B;

    fill(dist, dist + N, inf);

    for (int i = 0; i < B; ++i) {
        adj[S[i]].emplace_back(T[i], D[i]);
        adj[T[i]].emplace_back(S[i], D[i]);
    }
}

void ReceiveB(bool y) {
    b[Q++] = y;

    if ((Q - Last) == 9) {
        int d = 0;

        for (int i = 0; i < 9; ++i) {
            d |= b[Last + i] << i;
        }

//        cout << st.size() << endl;

        int nd = st.empty() ? inf : st.begin()->first - S;
        assert(nd >= 0);

        if (nd < d) {
            int v = st.begin()->second;
            st.erase(st.begin());
            upd(v);
            assert(!used[v]);
            used[v] = true;

            for (int i = 0; i < 9; ++i) {
                SendB(nd >> i & 1);
            }
            for (int i = 0; i < 11; ++i) {
                SendB(v >> i & 1);
            }

            S += nd;
            Last = Q;
        } else {
            for (int i = 0; i < 9; ++i) {
                SendB(1);
            }
        }
    } else if (Q - Last == 9 + 11) {
        int d = 0, v = 0;

        for (int i = 0; i < 9; ++i) {
            d |= b[Last + i] << i;
        }
        for (int i = 0; i < 11; ++i) {
            v |= b[Last + 9 + i] << i;
        }

        ckmin(v, S + d);
        used[v] = true;
        st.erase({dist[v], v});
        upd(v);

        S += d;

        Last = Q;
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	391 ms	1212 KB	Output is correct
2	Correct	1 ms	656 KB	Output is correct
3	Correct	516 ms	992 KB	Output is correct
4	Correct	370 ms	10176 KB	Output is correct
5	Correct	33 ms	912 KB	Output is correct
6	Correct	472 ms	2260 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	656 KB	Output is correct
2	Correct	418 ms	900 KB	Output is correct
3	Correct	494 ms	940 KB	Output is correct
4	Correct	689 ms	27760 KB	Output is correct
5	Correct	655 ms	24124 KB	Output is correct
6	Correct	120 ms	732 KB	Output is correct
7	Correct	697 ms	24336 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	511 ms	984 KB	Output is correct
2	Correct	2 ms	656 KB	Output is correct
3	Correct	597 ms	952 KB	Output is correct
4	Correct	331 ms	1020 KB	Output is correct
5	Correct	554 ms	1032 KB	Output is correct
6	Correct	494 ms	1000 KB	Output is correct
7	Correct	464 ms	832 KB	Output is correct
8	Correct	588 ms	964 KB	Output is correct
9	Correct	495 ms	836 KB	Output is correct
10	Correct	507 ms	1044 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	768 KB	Output is correct
2	Correct	261 ms	868 KB	Output is correct
3	Correct	240 ms	13332 KB	Output is correct
4	Correct	142 ms	800 KB	Output is correct
5	Correct	214 ms	10128 KB	Output is correct
6	Correct	239 ms	896 KB	Output is correct
7	Correct	238 ms	824 KB	Output is correct
8	Correct	176 ms	836 KB	Output is correct
9	Correct	307 ms	18208 KB	Output is correct
10	Correct	319 ms	18248 KB	Output is correct
11	Correct	459 ms	35768 KB	Output is correct
12	Correct	419 ms	30640 KB	Output is correct
13	Correct	150 ms	996 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	768 KB	Output is correct
2	Correct	261 ms	868 KB	Output is correct
3	Correct	240 ms	13332 KB	Output is correct
4	Correct	142 ms	800 KB	Output is correct
5	Correct	214 ms	10128 KB	Output is correct
6	Correct	239 ms	896 KB	Output is correct
7	Correct	238 ms	824 KB	Output is correct
8	Correct	176 ms	836 KB	Output is correct
9	Correct	307 ms	18208 KB	Output is correct
10	Correct	319 ms	18248 KB	Output is correct
11	Correct	459 ms	35768 KB	Output is correct
12	Correct	419 ms	30640 KB	Output is correct
13	Correct	150 ms	996 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	255 ms	772 KB	Output is correct
16	Correct	246 ms	880 KB	Output is correct
17	Correct	309 ms	756 KB	Output is correct
18	Correct	388 ms	10152 KB	Output is correct
19	Correct	235 ms	812 KB	Output is correct
20	Correct	364 ms	10388 KB	Output is correct
21	Correct	218 ms	976 KB	Output is correct
22	Correct	220 ms	988 KB	Output is correct
23	Correct	375 ms	22176 KB	Output is correct
24	Correct	546 ms	22192 KB	Output is correct
25	Correct	569 ms	43484 KB	Output is correct
26	Correct	509 ms	36400 KB	Output is correct
27	Correct	250 ms	1012 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	768 KB	Output is correct
2	Correct	261 ms	868 KB	Output is correct
3	Correct	240 ms	13332 KB	Output is correct
4	Correct	142 ms	800 KB	Output is correct
5	Correct	214 ms	10128 KB	Output is correct
6	Correct	239 ms	896 KB	Output is correct
7	Correct	238 ms	824 KB	Output is correct
8	Correct	176 ms	836 KB	Output is correct
9	Correct	307 ms	18208 KB	Output is correct
10	Correct	319 ms	18248 KB	Output is correct
11	Correct	459 ms	35768 KB	Output is correct
12	Correct	419 ms	30640 KB	Output is correct
13	Correct	150 ms	996 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	255 ms	772 KB	Output is correct
16	Correct	246 ms	880 KB	Output is correct
17	Correct	309 ms	756 KB	Output is correct
18	Correct	388 ms	10152 KB	Output is correct
19	Correct	235 ms	812 KB	Output is correct
20	Correct	364 ms	10388 KB	Output is correct
21	Correct	218 ms	976 KB	Output is correct
22	Correct	220 ms	988 KB	Output is correct
23	Correct	375 ms	22176 KB	Output is correct
24	Correct	546 ms	22192 KB	Output is correct
25	Correct	569 ms	43484 KB	Output is correct
26	Correct	509 ms	36400 KB	Output is correct
27	Correct	250 ms	1012 KB	Output is correct
28	Correct	355 ms	804 KB	Output is correct
29	Correct	341 ms	796 KB	Output is correct
30	Correct	518 ms	23960 KB	Output is correct
31	Correct	278 ms	892 KB	Output is correct
32	Correct	441 ms	21112 KB	Output is correct
33	Correct	195 ms	856 KB	Output is correct
34	Correct	299 ms	916 KB	Output is correct
35	Correct	411 ms	928 KB	Output is correct
36	Correct	434 ms	24748 KB	Output is correct
37	Correct	409 ms	24868 KB	Output is correct
38	Correct	665 ms	48896 KB	Output is correct
39	Correct	564 ms	44236 KB	Output is correct
40	Correct	305 ms	960 KB	Output is correct

Subtask #7
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	391 ms	1212 KB	Output is correct
2	Correct	1 ms	656 KB	Output is correct
3	Correct	516 ms	992 KB	Output is correct
4	Correct	370 ms	10176 KB	Output is correct
5	Correct	33 ms	912 KB	Output is correct
6	Correct	472 ms	2260 KB	Output is correct
7	Correct	1 ms	656 KB	Output is correct
8	Correct	418 ms	900 KB	Output is correct
9	Correct	494 ms	940 KB	Output is correct
10	Correct	689 ms	27760 KB	Output is correct
11	Correct	655 ms	24124 KB	Output is correct
12	Correct	120 ms	732 KB	Output is correct
13	Correct	697 ms	24336 KB	Output is correct
14	Correct	511 ms	984 KB	Output is correct
15	Correct	2 ms	656 KB	Output is correct
16	Correct	597 ms	952 KB	Output is correct
17	Correct	331 ms	1020 KB	Output is correct
18	Correct	554 ms	1032 KB	Output is correct
19	Correct	494 ms	1000 KB	Output is correct
20	Correct	464 ms	832 KB	Output is correct
21	Correct	588 ms	964 KB	Output is correct
22	Correct	495 ms	836 KB	Output is correct
23	Correct	507 ms	1044 KB	Output is correct
24	Correct	238 ms	768 KB	Output is correct
25	Correct	261 ms	868 KB	Output is correct
26	Correct	240 ms	13332 KB	Output is correct
27	Correct	142 ms	800 KB	Output is correct
28	Correct	214 ms	10128 KB	Output is correct
29	Correct	239 ms	896 KB	Output is correct
30	Correct	238 ms	824 KB	Output is correct
31	Correct	176 ms	836 KB	Output is correct
32	Correct	307 ms	18208 KB	Output is correct
33	Correct	319 ms	18248 KB	Output is correct
34	Correct	459 ms	35768 KB	Output is correct
35	Correct	419 ms	30640 KB	Output is correct
36	Correct	150 ms	996 KB	Output is correct
37	Correct	2 ms	656 KB	Output is correct
38	Correct	255 ms	772 KB	Output is correct
39	Correct	246 ms	880 KB	Output is correct
40	Correct	309 ms	756 KB	Output is correct
41	Correct	388 ms	10152 KB	Output is correct
42	Correct	235 ms	812 KB	Output is correct
43	Correct	364 ms	10388 KB	Output is correct
44	Correct	218 ms	976 KB	Output is correct
45	Correct	220 ms	988 KB	Output is correct
46	Correct	375 ms	22176 KB	Output is correct
47	Correct	546 ms	22192 KB	Output is correct
48	Correct	569 ms	43484 KB	Output is correct
49	Correct	509 ms	36400 KB	Output is correct
50	Correct	250 ms	1012 KB	Output is correct
51	Correct	355 ms	804 KB	Output is correct
52	Correct	341 ms	796 KB	Output is correct
53	Correct	518 ms	23960 KB	Output is correct
54	Correct	278 ms	892 KB	Output is correct
55	Correct	441 ms	21112 KB	Output is correct
56	Correct	195 ms	856 KB	Output is correct
57	Correct	299 ms	916 KB	Output is correct
58	Correct	411 ms	928 KB	Output is correct
59	Correct	434 ms	24748 KB	Output is correct
60	Correct	409 ms	24868 KB	Output is correct
61	Correct	665 ms	48896 KB	Output is correct
62	Correct	564 ms	44236 KB	Output is correct
63	Correct	305 ms	960 KB	Output is correct
64	Correct	329 ms	1064 KB	Output is correct
65	Correct	685 ms	26472 KB	Output is correct
66	Correct	586 ms	23328 KB	Output is correct
67	Correct	450 ms	1148 KB	Output is correct
68	Correct	484 ms	1148 KB	Output is correct
69	Correct	686 ms	47620 KB	Output is correct
70	Correct	734 ms	39544 KB	Output is correct
71	Correct	574 ms	5020 KB	Output is correct
72	Correct	507 ms	1344 KB	Output is correct

답안 #748618

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