Submission #218397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218397	2020-04-02T06:22:59 Z	rama_pang	Two Transportations (JOI19_transportations)	C++14	100 / 100	2154 ms	85384 KB

Azer
Baijan

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int WEIGHT = 9;
const int VERTEX = 11;
const int INF = (1 << WEIGHT) - 1;

struct edge_t {
  int v, w;
  edge_t() {}
  edge_t(int v, int w) : v(v), w(w) {}
};

int N;
vector<int> dist;
vector<bool> processed;
vector<vector<edge_t>> adj;

}  // namespace

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

  adj.resize(N);
  dist.assign(N, -1);
  processed.assign(N, false);

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

  dist[0] = 0;
  for (int i = 0; i < WEIGHT; i++) SendA(false);
}

void ReceiveA(bool x) {
  static int prv = 0; // previous vertex that was processed
  static int cur = 0; // current vertex to be processed
  static int diff = 0;

  static int all_bits = 9;
  static int received = 0;
  static int information = 0;

  static int cnt_processed = 0;

  static auto reset = [&](int BITS) {
    received = information = 0;
    all_bits = BITS;
  };

  received++;
  information = 2 * information + x;

  if (received < all_bits) return;

  // received all bits

  if (all_bits == WEIGHT) {
    if (diff <= information) { // the next vertex is from Azer, so we send its id to Baijan
      information = cur;
      received = all_bits = VERTEX;
      for (int i = VERTEX - 1; i >= 0; i--) SendA(cur & (1 << i));
    } else { // the next vertex is from Baijan, so we recieve its id
      diff = information;
      reset(VERTEX);
      return;
    }
  }

  if (all_bits == VERTEX) { // we should process current node and relax its edges
    cur = information;
    dist[cur] = dist[prv] + diff;
    processed[cur] = true;

    if ((++cnt_processed) == N) return;

    // relax edges
    for (auto &nxt : adj[cur]) {
      if (dist[nxt.v] == -1 || dist[nxt.v] > dist[cur] + nxt.w) {
        dist[nxt.v] = dist[cur] + nxt.w;
      }
    }

    int nxt = -1;
    for (int i = 0; i < N; i++) {
      if (processed[i] || dist[i] == -1) continue;
      if (nxt == -1 || dist[nxt] > dist[i]) nxt = i;
    }

    prv = cur;
    cur = nxt;
    diff = (cur == -1 ? INF : dist[cur] - dist[prv]);

    // recieve minimum weight from Baijan
    reset(WEIGHT);

    // send minimum weight to Baijan
    for (int i = WEIGHT - 1; i >= 0; i--) SendA(diff & (1 << i));
  }
}

vector<int> Answer() {
  vector<int> ans = dist;
  return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int WEIGHT = 9;
const int VERTEX = 11;
const int INF = (1 << WEIGHT) - 1;

struct edge_t {
  int v, w;
  edge_t() {}
  edge_t(int v, int w) : v(v), w(w) {}
};

int N;
vector<int> dist;
vector<bool> processed;
vector<vector<edge_t>> adj;

}  // namespace

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

  adj.resize(N);
  dist.assign(N, -1);
  processed.assign(N, false);

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

  dist[0] = 0;
  for (int i = 0; i < WEIGHT; i++) SendB(false);
}

void ReceiveB(bool y) {
  static int prv = 0; // previous vertex that was processed
  static int cur = 0; // current vertex to be processed
  static int diff = 0;

  static int all_bits = 9;
  static int received = 0;
  static int information = 0;

  static int cnt_processed = 0;

  static auto reset = [&](int BITS) {
    received = information = 0;
    all_bits = BITS;
  };

  received++;
  information = 2 * information + y;

  if (received < all_bits) return;

  // received all bits

  if (all_bits == WEIGHT) {
    if (diff < information) { // the next vertex is from Baijan, so we send its id to Azer
      information = cur;
      received = all_bits = VERTEX;
      for (int i = VERTEX - 1; i >= 0; i--) SendB(cur & (1 << i));
    } else { // the next vertex is from Azer, so we recieve its id
      diff = information;
      reset(VERTEX);
      return;
    }
  }

  if (all_bits == VERTEX) { // we should process current node and relax its edges
    cur = information;
    dist[cur] = dist[prv] + diff;
    processed[cur] = true;

    if ((++cnt_processed) == N) return;

    // relax edges
    for (auto &nxt : adj[cur]) {
      if (dist[nxt.v] == -1 || dist[nxt.v] > dist[cur] + nxt.w) {
        dist[nxt.v] = dist[cur] + nxt.w;
      }
    }

    int nxt = -1;
    for (int i = 0; i < N; i++) {
      if (processed[i] || dist[i] == -1) continue;
      if (nxt == -1 || dist[nxt] > dist[i]) nxt = i;
    }

    prv = cur;
    cur = nxt;
    diff = (cur == -1 ? INF : dist[cur] - dist[prv]);

    // recieve minimum weight from Azer
    reset(WEIGHT);

    // send minimum weight to Azer
    for (int i = WEIGHT - 1; i >= 0; i--) SendB(diff & (1 << i));
  }
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1028 ms	1792 KB	Output is correct
2	Correct	17 ms	1280 KB	Output is correct
3	Correct	1172 ms	1904 KB	Output is correct
4	Correct	1268 ms	20152 KB	Output is correct
5	Correct	70 ms	1536 KB	Output is correct
6	Correct	1112 ms	4576 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1536 KB	Output is correct
2	Correct	1100 ms	1736 KB	Output is correct
3	Correct	1072 ms	1864 KB	Output is correct
4	Correct	1472 ms	54768 KB	Output is correct
5	Correct	1436 ms	48272 KB	Output is correct
6	Correct	246 ms	1536 KB	Output is correct
7	Correct	1534 ms	48472 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1110 ms	1792 KB	Output is correct
2	Correct	18 ms	1192 KB	Output is correct
3	Correct	942 ms	1648 KB	Output is correct
4	Correct	1158 ms	1704 KB	Output is correct
5	Correct	912 ms	1976 KB	Output is correct
6	Correct	1200 ms	1536 KB	Output is correct
7	Correct	1004 ms	1536 KB	Output is correct
8	Correct	1070 ms	1792 KB	Output is correct
9	Correct	1156 ms	1856 KB	Output is correct
10	Correct	1116 ms	1856 KB	Output is correct

Subtask #4
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	554 ms	1608 KB	Output is correct
2	Correct	490 ms	1280 KB	Output is correct
3	Correct	714 ms	23688 KB	Output is correct
4	Correct	394 ms	1816 KB	Output is correct
5	Correct	708 ms	17224 KB	Output is correct
6	Correct	402 ms	1536 KB	Output is correct
7	Correct	522 ms	1792 KB	Output is correct
8	Correct	514 ms	1536 KB	Output is correct
9	Correct	856 ms	35824 KB	Output is correct
10	Correct	794 ms	36192 KB	Output is correct
11	Correct	1330 ms	61528 KB	Output is correct
12	Correct	1087 ms	53992 KB	Output is correct
13	Correct	630 ms	1536 KB	Output is correct
14	Correct	10 ms	1280 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	554 ms	1608 KB	Output is correct
2	Correct	490 ms	1280 KB	Output is correct
3	Correct	714 ms	23688 KB	Output is correct
4	Correct	394 ms	1816 KB	Output is correct
5	Correct	708 ms	17224 KB	Output is correct
6	Correct	402 ms	1536 KB	Output is correct
7	Correct	522 ms	1792 KB	Output is correct
8	Correct	514 ms	1536 KB	Output is correct
9	Correct	856 ms	35824 KB	Output is correct
10	Correct	794 ms	36192 KB	Output is correct
11	Correct	1330 ms	61528 KB	Output is correct
12	Correct	1087 ms	53992 KB	Output is correct
13	Correct	630 ms	1536 KB	Output is correct
14	Correct	10 ms	1280 KB	Output is correct
15	Correct	604 ms	1536 KB	Output is correct
16	Correct	663 ms	1536 KB	Output is correct
17	Correct	636 ms	1536 KB	Output is correct
18	Correct	868 ms	17776 KB	Output is correct
19	Correct	494 ms	1536 KB	Output is correct
20	Correct	866 ms	18144 KB	Output is correct
21	Correct	684 ms	1536 KB	Output is correct
22	Correct	476 ms	1592 KB	Output is correct
23	Correct	982 ms	43704 KB	Output is correct
24	Correct	1011 ms	43704 KB	Output is correct
25	Correct	1681 ms	74848 KB	Output is correct
26	Correct	1250 ms	64120 KB	Output is correct
27	Correct	672 ms	1536 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	554 ms	1608 KB	Output is correct
2	Correct	490 ms	1280 KB	Output is correct
3	Correct	714 ms	23688 KB	Output is correct
4	Correct	394 ms	1816 KB	Output is correct
5	Correct	708 ms	17224 KB	Output is correct
6	Correct	402 ms	1536 KB	Output is correct
7	Correct	522 ms	1792 KB	Output is correct
8	Correct	514 ms	1536 KB	Output is correct
9	Correct	856 ms	35824 KB	Output is correct
10	Correct	794 ms	36192 KB	Output is correct
11	Correct	1330 ms	61528 KB	Output is correct
12	Correct	1087 ms	53992 KB	Output is correct
13	Correct	630 ms	1536 KB	Output is correct
14	Correct	10 ms	1280 KB	Output is correct
15	Correct	604 ms	1536 KB	Output is correct
16	Correct	663 ms	1536 KB	Output is correct
17	Correct	636 ms	1536 KB	Output is correct
18	Correct	868 ms	17776 KB	Output is correct
19	Correct	494 ms	1536 KB	Output is correct
20	Correct	866 ms	18144 KB	Output is correct
21	Correct	684 ms	1536 KB	Output is correct
22	Correct	476 ms	1592 KB	Output is correct
23	Correct	982 ms	43704 KB	Output is correct
24	Correct	1011 ms	43704 KB	Output is correct
25	Correct	1681 ms	74848 KB	Output is correct
26	Correct	1250 ms	64120 KB	Output is correct
27	Correct	672 ms	1536 KB	Output is correct
28	Correct	818 ms	1464 KB	Output is correct
29	Correct	840 ms	1440 KB	Output is correct
30	Correct	1305 ms	41848 KB	Output is correct
31	Correct	662 ms	1536 KB	Output is correct
32	Correct	1132 ms	37456 KB	Output is correct
33	Correct	850 ms	1616 KB	Output is correct
34	Correct	812 ms	1792 KB	Output is correct
35	Correct	610 ms	2048 KB	Output is correct
36	Correct	1412 ms	49272 KB	Output is correct
37	Correct	1294 ms	49096 KB	Output is correct
38	Correct	1826 ms	85384 KB	Output is correct
39	Correct	1463 ms	78496 KB	Output is correct
40	Correct	740 ms	2304 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1028 ms	1792 KB	Output is correct
2	Correct	17 ms	1280 KB	Output is correct
3	Correct	1172 ms	1904 KB	Output is correct
4	Correct	1268 ms	20152 KB	Output is correct
5	Correct	70 ms	1536 KB	Output is correct
6	Correct	1112 ms	4576 KB	Output is correct
7	Correct	18 ms	1536 KB	Output is correct
8	Correct	1100 ms	1736 KB	Output is correct
9	Correct	1072 ms	1864 KB	Output is correct
10	Correct	1472 ms	54768 KB	Output is correct
11	Correct	1436 ms	48272 KB	Output is correct
12	Correct	246 ms	1536 KB	Output is correct
13	Correct	1534 ms	48472 KB	Output is correct
14	Correct	1110 ms	1792 KB	Output is correct
15	Correct	18 ms	1192 KB	Output is correct
16	Correct	942 ms	1648 KB	Output is correct
17	Correct	1158 ms	1704 KB	Output is correct
18	Correct	912 ms	1976 KB	Output is correct
19	Correct	1200 ms	1536 KB	Output is correct
20	Correct	1004 ms	1536 KB	Output is correct
21	Correct	1070 ms	1792 KB	Output is correct
22	Correct	1156 ms	1856 KB	Output is correct
23	Correct	1116 ms	1856 KB	Output is correct
24	Correct	554 ms	1608 KB	Output is correct
25	Correct	490 ms	1280 KB	Output is correct
26	Correct	714 ms	23688 KB	Output is correct
27	Correct	394 ms	1816 KB	Output is correct
28	Correct	708 ms	17224 KB	Output is correct
29	Correct	402 ms	1536 KB	Output is correct
30	Correct	522 ms	1792 KB	Output is correct
31	Correct	514 ms	1536 KB	Output is correct
32	Correct	856 ms	35824 KB	Output is correct
33	Correct	794 ms	36192 KB	Output is correct
34	Correct	1330 ms	61528 KB	Output is correct
35	Correct	1087 ms	53992 KB	Output is correct
36	Correct	630 ms	1536 KB	Output is correct
37	Correct	10 ms	1280 KB	Output is correct
38	Correct	604 ms	1536 KB	Output is correct
39	Correct	663 ms	1536 KB	Output is correct
40	Correct	636 ms	1536 KB	Output is correct
41	Correct	868 ms	17776 KB	Output is correct
42	Correct	494 ms	1536 KB	Output is correct
43	Correct	866 ms	18144 KB	Output is correct
44	Correct	684 ms	1536 KB	Output is correct
45	Correct	476 ms	1592 KB	Output is correct
46	Correct	982 ms	43704 KB	Output is correct
47	Correct	1011 ms	43704 KB	Output is correct
48	Correct	1681 ms	74848 KB	Output is correct
49	Correct	1250 ms	64120 KB	Output is correct
50	Correct	672 ms	1536 KB	Output is correct
51	Correct	818 ms	1464 KB	Output is correct
52	Correct	840 ms	1440 KB	Output is correct
53	Correct	1305 ms	41848 KB	Output is correct
54	Correct	662 ms	1536 KB	Output is correct
55	Correct	1132 ms	37456 KB	Output is correct
56	Correct	850 ms	1616 KB	Output is correct
57	Correct	812 ms	1792 KB	Output is correct
58	Correct	610 ms	2048 KB	Output is correct
59	Correct	1412 ms	49272 KB	Output is correct
60	Correct	1294 ms	49096 KB	Output is correct
61	Correct	1826 ms	85384 KB	Output is correct
62	Correct	1463 ms	78496 KB	Output is correct
63	Correct	740 ms	2304 KB	Output is correct
64	Correct	1002 ms	2048 KB	Output is correct
65	Correct	1458 ms	47336 KB	Output is correct
66	Correct	1556 ms	41176 KB	Output is correct
67	Correct	1006 ms	2048 KB	Output is correct
68	Correct	1126 ms	2048 KB	Output is correct
69	Correct	2154 ms	83512 KB	Output is correct
70	Correct	1900 ms	68200 KB	Output is correct
71	Correct	1356 ms	9408 KB	Output is correct
72	Correct	1142 ms	2560 KB	Output is correct

Submission #218397

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 8.0 / 8.0

Subtask #4 38.0 / 38.0

Subtask #5 14.0 / 14.0

Subtask #6 10.0 / 10.0

Subtask #7 16.0 / 16.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
8.0 / 8.0

Subtask #4
38.0 / 38.0

Subtask #5
14.0 / 14.0

Subtask #6
10.0 / 10.0

Subtask #7
16.0 / 16.0