oj.uz

Submission #820023

# Submission time Handle Problem Language Result Execution time Memory
820023 2023-08-10T17:58:00 Z Aldas25 Two Transportations (JOI19_transportations) C++14
6 / 100
 3000 ms 10108 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 306 ms 788 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 356 ms 788 KB Output is correct
4 Correct 427 ms 10108 KB Output is correct
5 Correct 23 ms 912 KB Output is correct
6 Correct 401 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 274 ms 744 KB Output is correct
3 Runtime error 3 ms 476 KB Execution killed with signal 13
4 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 306 ms 788 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 356 ms 788 KB Output is correct
4 Correct 427 ms 10108 KB Output is correct
5 Correct 23 ms 912 KB Output is correct
6 Correct 401 ms 2208 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 274 ms 744 KB Output is correct
9 Runtime error 3 ms 476 KB Execution killed with signal 13
10 Halted 0 ms 0 KB -