Submission #218396

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218396	2020-04-02T06:21:00 Z	rama_pang	Two Transportations (JOI19_transportations)	C++14	100 / 100	2150 ms	85368 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	1094 ms	1880 KB	Output is correct
2	Correct	18 ms	1024 KB	Output is correct
3	Correct	1182 ms	1920 KB	Output is correct
4	Correct	1172 ms	20200 KB	Output is correct
5	Correct	76 ms	1536 KB	Output is correct
6	Correct	1160 ms	4432 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1024 KB	Output is correct
2	Correct	1142 ms	1792 KB	Output is correct
3	Correct	1166 ms	1800 KB	Output is correct
4	Correct	1600 ms	54864 KB	Output is correct
5	Correct	1602 ms	48200 KB	Output is correct
6	Correct	216 ms	1280 KB	Output is correct
7	Correct	1660 ms	48504 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1004 ms	1816 KB	Output is correct
2	Correct	18 ms	1024 KB	Output is correct
3	Correct	923 ms	1848 KB	Output is correct
4	Correct	1188 ms	1792 KB	Output is correct
5	Correct	1138 ms	1792 KB	Output is correct
6	Correct	1118 ms	1640 KB	Output is correct
7	Correct	1156 ms	1536 KB	Output is correct
8	Correct	1310 ms	1792 KB	Output is correct
9	Correct	1156 ms	1848 KB	Output is correct
10	Correct	1200 ms	1888 KB	Output is correct

Subtask #4
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	1536 KB	Output is correct
2	Correct	542 ms	1280 KB	Output is correct
3	Correct	762 ms	23664 KB	Output is correct
4	Correct	556 ms	1536 KB	Output is correct
5	Correct	652 ms	17416 KB	Output is correct
6	Correct	535 ms	1536 KB	Output is correct
7	Correct	511 ms	1536 KB	Output is correct
8	Correct	504 ms	1536 KB	Output is correct
9	Correct	878 ms	35736 KB	Output is correct
10	Correct	812 ms	36008 KB	Output is correct
11	Correct	1214 ms	61320 KB	Output is correct
12	Correct	1036 ms	53800 KB	Output is correct
13	Correct	600 ms	1792 KB	Output is correct
14	Correct	18 ms	1280 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	1536 KB	Output is correct
2	Correct	542 ms	1280 KB	Output is correct
3	Correct	762 ms	23664 KB	Output is correct
4	Correct	556 ms	1536 KB	Output is correct
5	Correct	652 ms	17416 KB	Output is correct
6	Correct	535 ms	1536 KB	Output is correct
7	Correct	511 ms	1536 KB	Output is correct
8	Correct	504 ms	1536 KB	Output is correct
9	Correct	878 ms	35736 KB	Output is correct
10	Correct	812 ms	36008 KB	Output is correct
11	Correct	1214 ms	61320 KB	Output is correct
12	Correct	1036 ms	53800 KB	Output is correct
13	Correct	600 ms	1792 KB	Output is correct
14	Correct	18 ms	1280 KB	Output is correct
15	Correct	642 ms	1536 KB	Output is correct
16	Correct	630 ms	1536 KB	Output is correct
17	Correct	622 ms	1536 KB	Output is correct
18	Correct	788 ms	17600 KB	Output is correct
19	Correct	498 ms	1728 KB	Output is correct
20	Correct	730 ms	18064 KB	Output is correct
21	Correct	560 ms	1536 KB	Output is correct
22	Correct	614 ms	1792 KB	Output is correct
23	Correct	860 ms	43960 KB	Output is correct
24	Correct	1026 ms	43648 KB	Output is correct
25	Correct	1762 ms	74904 KB	Output is correct
26	Correct	1272 ms	64272 KB	Output is correct
27	Correct	616 ms	1536 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	1536 KB	Output is correct
2	Correct	542 ms	1280 KB	Output is correct
3	Correct	762 ms	23664 KB	Output is correct
4	Correct	556 ms	1536 KB	Output is correct
5	Correct	652 ms	17416 KB	Output is correct
6	Correct	535 ms	1536 KB	Output is correct
7	Correct	511 ms	1536 KB	Output is correct
8	Correct	504 ms	1536 KB	Output is correct
9	Correct	878 ms	35736 KB	Output is correct
10	Correct	812 ms	36008 KB	Output is correct
11	Correct	1214 ms	61320 KB	Output is correct
12	Correct	1036 ms	53800 KB	Output is correct
13	Correct	600 ms	1792 KB	Output is correct
14	Correct	18 ms	1280 KB	Output is correct
15	Correct	642 ms	1536 KB	Output is correct
16	Correct	630 ms	1536 KB	Output is correct
17	Correct	622 ms	1536 KB	Output is correct
18	Correct	788 ms	17600 KB	Output is correct
19	Correct	498 ms	1728 KB	Output is correct
20	Correct	730 ms	18064 KB	Output is correct
21	Correct	560 ms	1536 KB	Output is correct
22	Correct	614 ms	1792 KB	Output is correct
23	Correct	860 ms	43960 KB	Output is correct
24	Correct	1026 ms	43648 KB	Output is correct
25	Correct	1762 ms	74904 KB	Output is correct
26	Correct	1272 ms	64272 KB	Output is correct
27	Correct	616 ms	1536 KB	Output is correct
28	Correct	710 ms	1792 KB	Output is correct
29	Correct	776 ms	1536 KB	Output is correct
30	Correct	1348 ms	42072 KB	Output is correct
31	Correct	898 ms	1536 KB	Output is correct
32	Correct	1216 ms	37376 KB	Output is correct
33	Correct	686 ms	2144 KB	Output is correct
34	Correct	820 ms	2048 KB	Output is correct
35	Correct	644 ms	1704 KB	Output is correct
36	Correct	1386 ms	49152 KB	Output is correct
37	Correct	1418 ms	49296 KB	Output is correct
38	Correct	1674 ms	85368 KB	Output is correct
39	Correct	1706 ms	78504 KB	Output is correct
40	Correct	838 ms	2048 KB	Output is correct

Subtask #7
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1094 ms	1880 KB	Output is correct
2	Correct	18 ms	1024 KB	Output is correct
3	Correct	1182 ms	1920 KB	Output is correct
4	Correct	1172 ms	20200 KB	Output is correct
5	Correct	76 ms	1536 KB	Output is correct
6	Correct	1160 ms	4432 KB	Output is correct
7	Correct	16 ms	1024 KB	Output is correct
8	Correct	1142 ms	1792 KB	Output is correct
9	Correct	1166 ms	1800 KB	Output is correct
10	Correct	1600 ms	54864 KB	Output is correct
11	Correct	1602 ms	48200 KB	Output is correct
12	Correct	216 ms	1280 KB	Output is correct
13	Correct	1660 ms	48504 KB	Output is correct
14	Correct	1004 ms	1816 KB	Output is correct
15	Correct	18 ms	1024 KB	Output is correct
16	Correct	923 ms	1848 KB	Output is correct
17	Correct	1188 ms	1792 KB	Output is correct
18	Correct	1138 ms	1792 KB	Output is correct
19	Correct	1118 ms	1640 KB	Output is correct
20	Correct	1156 ms	1536 KB	Output is correct
21	Correct	1310 ms	1792 KB	Output is correct
22	Correct	1156 ms	1848 KB	Output is correct
23	Correct	1200 ms	1888 KB	Output is correct
24	Correct	530 ms	1536 KB	Output is correct
25	Correct	542 ms	1280 KB	Output is correct
26	Correct	762 ms	23664 KB	Output is correct
27	Correct	556 ms	1536 KB	Output is correct
28	Correct	652 ms	17416 KB	Output is correct
29	Correct	535 ms	1536 KB	Output is correct
30	Correct	511 ms	1536 KB	Output is correct
31	Correct	504 ms	1536 KB	Output is correct
32	Correct	878 ms	35736 KB	Output is correct
33	Correct	812 ms	36008 KB	Output is correct
34	Correct	1214 ms	61320 KB	Output is correct
35	Correct	1036 ms	53800 KB	Output is correct
36	Correct	600 ms	1792 KB	Output is correct
37	Correct	18 ms	1280 KB	Output is correct
38	Correct	642 ms	1536 KB	Output is correct
39	Correct	630 ms	1536 KB	Output is correct
40	Correct	622 ms	1536 KB	Output is correct
41	Correct	788 ms	17600 KB	Output is correct
42	Correct	498 ms	1728 KB	Output is correct
43	Correct	730 ms	18064 KB	Output is correct
44	Correct	560 ms	1536 KB	Output is correct
45	Correct	614 ms	1792 KB	Output is correct
46	Correct	860 ms	43960 KB	Output is correct
47	Correct	1026 ms	43648 KB	Output is correct
48	Correct	1762 ms	74904 KB	Output is correct
49	Correct	1272 ms	64272 KB	Output is correct
50	Correct	616 ms	1536 KB	Output is correct
51	Correct	710 ms	1792 KB	Output is correct
52	Correct	776 ms	1536 KB	Output is correct
53	Correct	1348 ms	42072 KB	Output is correct
54	Correct	898 ms	1536 KB	Output is correct
55	Correct	1216 ms	37376 KB	Output is correct
56	Correct	686 ms	2144 KB	Output is correct
57	Correct	820 ms	2048 KB	Output is correct
58	Correct	644 ms	1704 KB	Output is correct
59	Correct	1386 ms	49152 KB	Output is correct
60	Correct	1418 ms	49296 KB	Output is correct
61	Correct	1674 ms	85368 KB	Output is correct
62	Correct	1706 ms	78504 KB	Output is correct
63	Correct	838 ms	2048 KB	Output is correct
64	Correct	1166 ms	2048 KB	Output is correct
65	Correct	1608 ms	47488 KB	Output is correct
66	Correct	1650 ms	41136 KB	Output is correct
67	Correct	1136 ms	2304 KB	Output is correct
68	Correct	1033 ms	2048 KB	Output is correct
69	Correct	2150 ms	83696 KB	Output is correct
70	Correct	1894 ms	68024 KB	Output is correct
71	Correct	1283 ms	9168 KB	Output is correct
72	Correct	1080 ms	2560 KB	Output is correct

Submission #218396

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