oj.uz

Submission #821671

# Submission time Handle Problem Language Result Execution time Memory
821671 2023-08-11T12:51:24 Z Aldas25 Two Transportations (JOI19_transportations) C++14
6 / 100
 3000 ms 27540 KB 
#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace A {

    const int MAXN = 2100;
    const int BITS_IN_DISTANCES = 9;
    const int BITS_IN_VERTICES = 11;
    const int INF_DISTANCE = (1 << BITS_IN_DISTANCES) - 1;

    int d[MAXN];
    bool vis[MAXN];
    int n;
    vector<pair<int, int>> adj[MAXN];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    int longestCommonDistance = 0;
    pair<int, int> nextShortest;
    int distancesKnown = 0;

    int distanceReceived = 0;
    int vertexReceived = 0;
    int receivedBitsCount = 0;
    bool gettingDistance = true; // true if receiveA gets bits for distances, false if receiveA gets bits for vertex number

    void sendNumber(int number, int bits) {
        for (int i = 0; i < bits; i++) {
            SendA(number & (1 << i));
        }
    }

    void sendNextShortest() {
        int distance = nextShortest.first - longestCommonDistance; // subtract to fit in BITS_IN_DISTANCES bytes
        sendNumber(distance, BITS_IN_DISTANCES);
    }

    void cleanPq() {
        while (!pq.empty() && vis[pq.top().second]) { // don't consider if already distance known (if vis[v] is true)
            pq.pop();
        }
    }

    void startSending() {
        cleanPq();
        int v = pq.top().second; // both people now know that the next shortest distance is to v
        pq.pop();
        longestCommonDistance = d[v];
        vis[v] = true;
        distancesKnown++;

        if (distancesKnown == n) return; // we now know all distances

        for (auto p : adj[v]) {
            int u = p.first;
            int w = p.second;

            int newDist = d[v] + w;
            if (d[u] == -1 || d[u] > newDist) {
                d[u] = newDist;
                pq.emplace(d[u], u);
            }
        }

        cleanPq();
        if (pq.empty()) nextShortest = {INF_DISTANCE + longestCommonDistance, n};
        else nextShortest = pq.top();

        sendNextShortest();
    }

    void distanceWasReceived() {
        distanceReceived += longestCommonDistance; // because it was subtracted before sending

        if (distanceReceived < nextShortest.first) { // in equality case, Azer will send vertex number
            // we should now expect bits for the vertex number
            gettingDistance = false;
        } else {
            // we have better distance, we will send the vertex number of it
            gettingDistance = true;
            distanceReceived = 0;
            sendNumber(nextShortest.second, BITS_IN_VERTICES);
            startSending();
        }
    }

    void vertexWasReceived() {
        if (d[vertexReceived] == -1 || distanceReceived < d[vertexReceived]) {
            d[vertexReceived] = distanceReceived;
            pq.emplace(distanceReceived, vertexReceived);
        }

        gettingDistance = true;
        distanceReceived = 0;
        vertexReceived = 0;

        startSending();
    }

    void receiveBitForDistance(bool x) {
        if (x) distanceReceived += (1 << receivedBitsCount);
        receivedBitsCount++;

        if (receivedBitsCount == BITS_IN_DISTANCES) { // distance was got
            receivedBitsCount = 0;
            distanceWasReceived();
        }
    }

    void receiveBitForVertex(bool x) {
        if (x) vertexReceived += (1 << receivedBitsCount);
        receivedBitsCount++;

        if (receivedBitsCount == BITS_IN_VERTICES) { // vertex was got
            receivedBitsCount = 0;
            vertexWasReceived();
        }
    }

    void receiveBit(bool x) {
        if (gettingDistance)
            receiveBitForDistance(x);
        else
            receiveBitForVertex(x);
    }

}  // namespace

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

  for (int i = 0; i < N; i++) {
      A::d[i] = -1;
  }

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

  A::d[0] = 0;
  A::pq.emplace(0, 0);

  A::startSending();
}

void ReceiveA(bool x) {
    A::receiveBit(x);
}

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

/*


 7 1 5
 0 5 10
 5 4 10
 4 1 10
 1 3 10
 3 2 10
 6 0 10

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

using namespace std;

namespace B {

    const int MAXN = 2100;
    const int BITS_IN_DISTANCES = 9;
    const int BITS_IN_VERTICES = 11;
    const int INF_DISTANCE = (1 << BITS_IN_DISTANCES) - 1;

    int d[MAXN];
    bool vis[MAXN];
    int n;
    vector<pair<int, int>> adj[MAXN];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    int longestCommonDistance = 0;
    pair<int, int> nextShortest;
    int distancesKnown = 0;

    int distanceReceived = 0;
    int vertexReceived = 0;
    int receivedBitsCount = 0;
    bool gettingDistance = true; // true if receiveA gets bits for distances, false if receiveA gets bits for vertex number

    void sendNumber(int number, int bits) {
        for (int i = 0; i < bits; i++) {
            SendB(number & (1 << i));
        }
    }

    void sendNextShortest() {
        int distance = nextShortest.first - longestCommonDistance; // subtract to fit in BITS_IN_DISTANCES bytes
        sendNumber(distance, BITS_IN_DISTANCES);
    }

    void cleanPq() {
        while (!pq.empty() && vis[pq.top().second]) { // don't consider if already distance known (if vis[v] is true)
            pq.pop();
        }
    }

    void startSending() {
        cleanPq();
        int v = pq.top().second; // both people now know that the next shortest distance is to v
        pq.pop();
        longestCommonDistance = d[v];
        vis[v] = true;
        distancesKnown++;

        if (distancesKnown == n) return; // we now know all distances

        for (auto p : adj[v]) {
            int u = p.first;
            int w = p.second;

            int newDist = d[v] + w;
            if (d[u] == -1 || d[u] > newDist) {
                d[u] = newDist;
                pq.emplace(d[u], u);
            }
        }

        cleanPq();
        if (pq.empty()) nextShortest = {INF_DISTANCE + longestCommonDistance, n};
        else nextShortest = pq.top();

        sendNextShortest();
    }

    void distanceWasReceived() {
        distanceReceived += longestCommonDistance; // because it was subtracted before sending

        if (distanceReceived <= nextShortest.first) { // in equality case, Azer will send vertex number
            // we should now expect bits for the vertex number
            gettingDistance = false;
        } else {
            // we have better distance, we will send the vertex number of it
            gettingDistance = true;
            distanceReceived = 0;
            sendNumber(nextShortest.second, BITS_IN_VERTICES);
            startSending();
        }
    }

    void vertexWasReceived() {
        if (d[vertexReceived] == -1 || distanceReceived < d[vertexReceived]) {
            d[vertexReceived] = distanceReceived;
            pq.emplace(distanceReceived, vertexReceived);
        }

        gettingDistance = true;
        distanceReceived = 0;
        vertexReceived = 0;

        startSending();
    }

    void receiveBitForDistance(bool x) {
        if (x) distanceReceived += (1 << receivedBitsCount);
        receivedBitsCount++;

        if (receivedBitsCount == BITS_IN_DISTANCES) { // distance was got
            receivedBitsCount = 0;
            distanceWasReceived();
        }
    }

    void receiveBitForVertex(bool x) {
        if (x) vertexReceived += (1 << receivedBitsCount);
        receivedBitsCount++;

        if (receivedBitsCount == BITS_IN_VERTICES) { // vertex was got
            receivedBitsCount = 0;
            vertexWasReceived();
        }
    }

    void receiveBit(bool x) {
        if (gettingDistance)
            receiveBitForDistance(x);
        else
            receiveBitForVertex(x);
    }

}  // namespace

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

    for (int i = 0; i < N; i++) {
        B::d[i] = -1;
    }

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

    B::d[0] = 0;
    B::pq.emplace(0, 0);

    B::startSending();
}

void ReceiveB(bool y) {
    B::receiveBit(y);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 784 KB Output is correct
2 Correct 0 ms 712 KB Output is correct
3 Correct 405 ms 792 KB Output is correct
4 Correct 394 ms 10108 KB Output is correct
5 Correct 25 ms 912 KB Output is correct
6 Correct 393 ms 2208 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 656 KB Output is correct
2 Correct 461 ms 744 KB Output is correct
3 Correct 402 ms 844 KB Output is correct
4 Correct 438 ms 27540 KB Output is correct
5 Correct 623 ms 24080 KB Output is correct
6 Correct 99 ms 656 KB Output is correct
7 Incorrect 496 ms 24396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 784 KB Output is correct
2 Correct 0 ms 712 KB Output is correct
3 Correct 405 ms 792 KB Output is correct
4 Correct 394 ms 10108 KB Output is correct
5 Correct 25 ms 912 KB Output is correct
6 Correct 393 ms 2208 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 461 ms 744 KB Output is correct
9 Correct 402 ms 844 KB Output is correct
10 Correct 438 ms 27540 KB Output is correct
11 Correct 623 ms 24080 KB Output is correct
12 Correct 99 ms 656 KB Output is correct
13 Incorrect 496 ms 24396 KB Output isn't correct
14 Halted 0 ms 0 KB -