oj.uz

Submission #821664

# Submission time Handle Problem Language Result Execution time Memory
821664 2023-08-11T12:45:22 Z Aldas25 Two Transportations (JOI19_transportations) C++14
6 / 100
 3000 ms 27524 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 startSending() {
        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);
            }
        }

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


        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 startSending() {
        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);
            }
        }

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


        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 360 ms 800 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 434 ms 816 KB Output is correct
4 Correct 481 ms 10116 KB Output is correct
5 Correct 23 ms 912 KB Output is correct
6 Correct 429 ms 2200 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 407 ms 756 KB Output is correct
3 Correct 413 ms 804 KB Output is correct
4 Correct 486 ms 27524 KB Output is correct
5 Correct 498 ms 24064 KB Output is correct
6 Correct 99 ms 656 KB Output is correct
7 Incorrect 499 ms 24208 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 360 ms 800 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 434 ms 816 KB Output is correct
4 Correct 481 ms 10116 KB Output is correct
5 Correct 23 ms 912 KB Output is correct
6 Correct 429 ms 2200 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 407 ms 756 KB Output is correct
9 Correct 413 ms 804 KB Output is correct
10 Correct 486 ms 27524 KB Output is correct
11 Correct 498 ms 24064 KB Output is correct
12 Correct 99 ms 656 KB Output is correct
13 Incorrect 499 ms 24208 KB Output isn't correct
14 Halted 0 ms 0 KB -