oj.uz

답안 #748501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748501 2023-05-26T11:32:17 Z piOOE Two Transportations (JOI19_transportations) C++17
6 / 100
 3000 ms 10268 KB 
#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);
            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;
        }

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

    if (Q == Last) {
        if (st.empty() && 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;

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

//            cout << "B gives: " << v << " " << S << "+" << nd << endl;

            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});

//        cout << "B received: " << v << " " << S << "+" << d << endl;

        S += d;

        Last = Q;
    }
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 952 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 493 ms 1196 KB Output is correct
4 Correct 501 ms 10268 KB Output is correct
5 Correct 26 ms 912 KB Output is correct
6 Correct 485 ms 2396 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 656 KB Output is correct
2 Execution timed out 3000 ms 328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3000 ms 428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 952 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 493 ms 1196 KB Output is correct
4 Correct 501 ms 10268 KB Output is correct
5 Correct 26 ms 912 KB Output is correct
6 Correct 485 ms 2396 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Execution timed out 3000 ms 328 KB Time limit exceeded
9 Halted 0 ms 0 KB -