oj.uz

Submission #820032

# Submission time Handle Problem Language Result Execution time Memory
820032 2023-08-10T18:12:23 Z Aldas25 Two Transportations (JOI19_transportations) C++14
6 / 100
 3000 ms 27544 KB 
#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

    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) {
  n = N;

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

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

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

  startSending();
}

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

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

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

using namespace std;

namespace {

    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) {
    n = N;

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

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

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

    startSending();
}

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 788 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 404 ms 800 KB Output is correct
4 Correct 420 ms 10128 KB Output is correct
5 Correct 22 ms 912 KB Output is correct
6 Correct 333 ms 2216 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 322 ms 740 KB Output is correct
3 Correct 350 ms 808 KB Output is correct
4 Correct 536 ms 27544 KB Output is correct
5 Correct 629 ms 24076 KB Output is correct
6 Correct 90 ms 656 KB Output is correct
7 Incorrect 490 ms 24404 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 434 ms 788 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 404 ms 800 KB Output is correct
4 Correct 420 ms 10128 KB Output is correct
5 Correct 22 ms 912 KB Output is correct
6 Correct 333 ms 2216 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 322 ms 740 KB Output is correct
9 Correct 350 ms 808 KB Output is correct
10 Correct 536 ms 27544 KB Output is correct
11 Correct 629 ms 24076 KB Output is correct
12 Correct 90 ms 656 KB Output is correct
13 Incorrect 490 ms 24404 KB Output isn't correct
14 Halted 0 ms 0 KB -