oj.uz

Submission #579122

# Submission time Handle Problem Language Result Execution time Memory
579122 2022-06-18T11:57:40 Z Lucpp Two Transportations (JOI19_transportations) C++17
100 / 100
 895 ms 48652 KB 
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

namespace {

int N;
vector<vector<pair<int, int>>> g;
vector<int> dist;
vector<bool> vis;
queue<bool> received;
int numRecv;
int curDist = 0;
int numVisited = 0;
int nxt, nxtDist;

void sendInt(int x, int bits){
  for(int i = 0; i < bits; i++){
    bool b = x & (1<<i);
    SendA(b);
  }
}

void visit(int u){
  numVisited++;
  vis[u] = true;
  curDist = dist[u];
  for(auto [v, c] : g[u]){
    dist[v] = min(dist[v], dist[u]+c);
  }
  if(numVisited == N) return;

  nxt = -1, nxtDist = INF;
  for(int i = 0; i < N; i++){
    if(!vis[i] && dist[i] < nxtDist){
      nxtDist = dist[i];
      nxt = i;
    }
  }
  int x = min(nxtDist-curDist, 501);
  numRecv = 9;
  sendInt(x, 9);
}

int receiveInt(int bits){
  int ans = 0;
  for(int i = 0; i < bits; i++){
    bool b = received.front(); received.pop();
    if(b) ans += (1<<i);
  }
  // cerr << "A " << ans << " " << bits << endl;
  return ans;
}

void receive(){
  if(numRecv == 9){
    int x = receiveInt(9);
    int otherDist = x+curDist;
    if(otherDist < nxtDist){
      nxtDist = otherDist;
      numRecv = 11;
    }
    else{
      sendInt(nxt, 11);
      visit(nxt);
    }
  }
  else if(numRecv == 11){
    nxt = receiveInt(11);
    dist[nxt] = nxtDist;
    visit(nxt);
  }
}

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::N = N;
  g.resize(N);
  for (int i = 0; i < A; ++i) {
    g[U[i]].emplace_back(V[i], C[i]);
    g[V[i]].emplace_back(U[i], C[i]);
  }
  dist.assign(N, INF);
  dist[0] = 0;
  vis.resize(N);
  ::visit(0);
}

void ReceiveA(bool x) {
  received.push(x);
  if((int)received.size() == numRecv){
    ::receive();
  }
}

std::vector<int> Answer() {
  return dist;
}

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

namespace {

int N;
vector<vector<pair<int, int>>> g;
vector<int> dist;
vector<bool> vis;
queue<bool> received;
int numRecv;
int curDist = 0;
int numVisited = 0;
int nxt, nxtDist;

void sendInt(int x, int bits){
  for(int i = 0; i < bits; i++){
    bool b = x & (1<<i);
    SendB(b);
  }
}

void visit(int u){
  numVisited++;
  vis[u] = true;
  curDist = dist[u];
  for(auto [v, c] : g[u]){
    dist[v] = min(dist[v], dist[u]+c);
  }
  if(numVisited == N) return;

  nxt = -1, nxtDist = INF;
  for(int i = 0; i < N; i++){
    if(!vis[i] && dist[i] < nxtDist){
      nxtDist = dist[i];
      nxt = i;
    }
  }
  int x = min(nxtDist-curDist, 501);
  numRecv = 9;
  sendInt(x, 9);
}

int receiveInt(int bits){
  int ans = 0;
  for(int i = 0; i < bits; i++){
    bool b = received.front(); received.pop();
    if(b) ans += (1<<i);
  }
  // cerr << "B " << ans << " " << bits << endl;
  return ans;
}

void receive(){
  if(numRecv == 9){
    int x = receiveInt(9);
    int otherDist = x+curDist;
    if(otherDist <= nxtDist){
      nxtDist = otherDist;
      numRecv = 11;
    }
    else{
      sendInt(nxt, 11);
      visit(nxt);
    }
  }
  else if(numRecv == 11){
    nxt = receiveInt(11);
    dist[nxt] = nxtDist;
    visit(nxt);
  }
}

}  // namespace

void InitB(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::N = N;
  g.resize(N);
  for (int i = 0; i < A; ++i) {
    g[U[i]].emplace_back(V[i], C[i]);
    g[V[i]].emplace_back(U[i], C[i]);
  }
  dist.assign(N, INF);
  dist[0] = 0;
  vis.resize(N);
  vis[0] = true;
  ::visit(0);
}

void ReceiveB(bool x) {
  received.push(x);
  if((int)received.size() == numRecv){
    ::receive();
  }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 792 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 460 ms 788 KB Output is correct
4 Correct 508 ms 10112 KB Output is correct
5 Correct 27 ms 656 KB Output is correct
6 Correct 548 ms 2148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 400 KB Output is correct
2 Correct 396 ms 744 KB Output is correct
3 Correct 415 ms 804 KB Output is correct
4 Correct 689 ms 27400 KB Output is correct
5 Correct 715 ms 24104 KB Output is correct
6 Correct 126 ms 620 KB Output is correct
7 Correct 584 ms 24224 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 724 KB Output is correct
2 Correct 0 ms 420 KB Output is correct
3 Correct 506 ms 660 KB Output is correct
4 Correct 520 ms 864 KB Output is correct
5 Correct 559 ms 656 KB Output is correct
6 Correct 402 ms 740 KB Output is correct
7 Correct 562 ms 740 KB Output is correct
8 Correct 491 ms 676 KB Output is correct
9 Correct 448 ms 656 KB Output is correct
10 Correct 482 ms 788 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 656 KB Output is correct
2 Correct 236 ms 632 KB Output is correct
3 Correct 283 ms 13336 KB Output is correct
4 Correct 203 ms 684 KB Output is correct
5 Correct 218 ms 9904 KB Output is correct
6 Correct 252 ms 656 KB Output is correct
7 Correct 227 ms 656 KB Output is correct
8 Correct 239 ms 700 KB Output is correct
9 Correct 320 ms 17968 KB Output is correct
10 Correct 334 ms 18136 KB Output is correct
11 Correct 459 ms 35536 KB Output is correct
12 Correct 368 ms 30680 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 656 KB Output is correct
2 Correct 236 ms 632 KB Output is correct
3 Correct 283 ms 13336 KB Output is correct
4 Correct 203 ms 684 KB Output is correct
5 Correct 218 ms 9904 KB Output is correct
6 Correct 252 ms 656 KB Output is correct
7 Correct 227 ms 656 KB Output is correct
8 Correct 239 ms 700 KB Output is correct
9 Correct 320 ms 17968 KB Output is correct
10 Correct 334 ms 18136 KB Output is correct
11 Correct 459 ms 35536 KB Output is correct
12 Correct 368 ms 30680 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 321 ms 656 KB Output is correct
16 Correct 319 ms 576 KB Output is correct
17 Correct 276 ms 528 KB Output is correct
18 Correct 343 ms 10060 KB Output is correct
19 Correct 271 ms 656 KB Output is correct
20 Correct 359 ms 10220 KB Output is correct
21 Correct 286 ms 656 KB Output is correct
22 Correct 243 ms 712 KB Output is correct
23 Correct 415 ms 22036 KB Output is correct
24 Correct 501 ms 22080 KB Output is correct
25 Correct 583 ms 43660 KB Output is correct
26 Correct 591 ms 36236 KB Output is correct
27 Correct 289 ms 732 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 656 KB Output is correct
2 Correct 236 ms 632 KB Output is correct
3 Correct 283 ms 13336 KB Output is correct
4 Correct 203 ms 684 KB Output is correct
5 Correct 218 ms 9904 KB Output is correct
6 Correct 252 ms 656 KB Output is correct
7 Correct 227 ms 656 KB Output is correct
8 Correct 239 ms 700 KB Output is correct
9 Correct 320 ms 17968 KB Output is correct
10 Correct 334 ms 18136 KB Output is correct
11 Correct 459 ms 35536 KB Output is correct
12 Correct 368 ms 30680 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 321 ms 656 KB Output is correct
16 Correct 319 ms 576 KB Output is correct
17 Correct 276 ms 528 KB Output is correct
18 Correct 343 ms 10060 KB Output is correct
19 Correct 271 ms 656 KB Output is correct
20 Correct 359 ms 10220 KB Output is correct
21 Correct 286 ms 656 KB Output is correct
22 Correct 243 ms 712 KB Output is correct
23 Correct 415 ms 22036 KB Output is correct
24 Correct 501 ms 22080 KB Output is correct
25 Correct 583 ms 43660 KB Output is correct
26 Correct 591 ms 36236 KB Output is correct
27 Correct 289 ms 732 KB Output is correct
28 Correct 330 ms 692 KB Output is correct
29 Correct 430 ms 676 KB Output is correct
30 Correct 592 ms 23976 KB Output is correct
31 Correct 353 ms 656 KB Output is correct
32 Correct 463 ms 20992 KB Output is correct
33 Correct 383 ms 716 KB Output is correct
34 Correct 352 ms 744 KB Output is correct
35 Correct 326 ms 752 KB Output is correct
36 Correct 604 ms 24652 KB Output is correct
37 Correct 521 ms 24684 KB Output is correct
38 Correct 679 ms 48652 KB Output is correct
39 Correct 655 ms 44032 KB Output is correct
40 Correct 391 ms 784 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 792 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 460 ms 788 KB Output is correct
4 Correct 508 ms 10112 KB Output is correct
5 Correct 27 ms 656 KB Output is correct
6 Correct 548 ms 2148 KB Output is correct
7 Correct 0 ms 400 KB Output is correct
8 Correct 396 ms 744 KB Output is correct
9 Correct 415 ms 804 KB Output is correct
10 Correct 689 ms 27400 KB Output is correct
11 Correct 715 ms 24104 KB Output is correct
12 Correct 126 ms 620 KB Output is correct
13 Correct 584 ms 24224 KB Output is correct
14 Correct 533 ms 724 KB Output is correct
15 Correct 0 ms 420 KB Output is correct
16 Correct 506 ms 660 KB Output is correct
17 Correct 520 ms 864 KB Output is correct
18 Correct 559 ms 656 KB Output is correct
19 Correct 402 ms 740 KB Output is correct
20 Correct 562 ms 740 KB Output is correct
21 Correct 491 ms 676 KB Output is correct
22 Correct 448 ms 656 KB Output is correct
23 Correct 482 ms 788 KB Output is correct
24 Correct 225 ms 656 KB Output is correct
25 Correct 236 ms 632 KB Output is correct
26 Correct 283 ms 13336 KB Output is correct
27 Correct 203 ms 684 KB Output is correct
28 Correct 218 ms 9904 KB Output is correct
29 Correct 252 ms 656 KB Output is correct
30 Correct 227 ms 656 KB Output is correct
31 Correct 239 ms 700 KB Output is correct
32 Correct 320 ms 17968 KB Output is correct
33 Correct 334 ms 18136 KB Output is correct
34 Correct 459 ms 35536 KB Output is correct
35 Correct 368 ms 30680 KB Output is correct
36 Correct 183 ms 656 KB Output is correct
37 Correct 0 ms 400 KB Output is correct
38 Correct 321 ms 656 KB Output is correct
39 Correct 319 ms 576 KB Output is correct
40 Correct 276 ms 528 KB Output is correct
41 Correct 343 ms 10060 KB Output is correct
42 Correct 271 ms 656 KB Output is correct
43 Correct 359 ms 10220 KB Output is correct
44 Correct 286 ms 656 KB Output is correct
45 Correct 243 ms 712 KB Output is correct
46 Correct 415 ms 22036 KB Output is correct
47 Correct 501 ms 22080 KB Output is correct
48 Correct 583 ms 43660 KB Output is correct
49 Correct 591 ms 36236 KB Output is correct
50 Correct 289 ms 732 KB Output is correct
51 Correct 330 ms 692 KB Output is correct
52 Correct 430 ms 676 KB Output is correct
53 Correct 592 ms 23976 KB Output is correct
54 Correct 353 ms 656 KB Output is correct
55 Correct 463 ms 20992 KB Output is correct
56 Correct 383 ms 716 KB Output is correct
57 Correct 352 ms 744 KB Output is correct
58 Correct 326 ms 752 KB Output is correct
59 Correct 604 ms 24652 KB Output is correct
60 Correct 521 ms 24684 KB Output is correct
61 Correct 679 ms 48652 KB Output is correct
62 Correct 655 ms 44032 KB Output is correct
63 Correct 391 ms 784 KB Output is correct
64 Correct 538 ms 956 KB Output is correct
65 Correct 719 ms 26620 KB Output is correct
66 Correct 758 ms 23324 KB Output is correct
67 Correct 602 ms 940 KB Output is correct
68 Correct 696 ms 928 KB Output is correct
69 Correct 895 ms 47648 KB Output is correct
70 Correct 653 ms 39512 KB Output is correct
71 Correct 590 ms 4932 KB Output is correct
72 Correct 507 ms 1184 KB Output is correct