oj.uz

Submission #957360

# Submission time Handle Problem Language Result Execution time Memory
957360 2024-04-03T14:31:58 Z Soumya1 Two Transportations (JOI19_transportations) C++17
14 / 100
 3000 ms 35808 KB 
#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2005;
const int inf = mxN * 500;
vector<pair<int, int>> ad[mxN];
int n;
int dist[mxN];
int cur_dist = 0;
bool done[mxN];
void send_node(int u) {
  for (int i = 0; i < 11; i++) {
    SendA(u >> i & 1);
  }
}
void send_weight(int w) {
  w = min(w, 511);
  for (int i = 0; i < 9; i++) {
    SendA(w >> i & 1);
  }
}
pair<int, int> get_best() {
  int who = -1, cur = inf;
  for (int i = 0; i < n; i++) {
    if (!done[i]) continue;
    for (auto [j, w] : ad[i]) {
      if (done[j]) continue;
      if (dist[i] + w < cur) {
        cur = dist[i] + w;
        who = j;
      }
    }
  }
  return {who, cur};
}
int need;
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 < A; i++) {
    ad[U[i]].push_back({V[i], C[i]});
    ad[V[i]].push_back({U[i], C[i]});
  }
  for (int i = 0; i < n; i++) {
    dist[i] = inf;
  }
  dist[0] = 0;
  done[0] = 1;
  int need = n - 1;
  if (need) send_weight(get_best().second);
}
bool rem() {
  for (int i = 0; i < n; i++) {
    if (!done[i]) return true;
  }
  return false;
}
int now = 1;
vector<int> store;
int cnt = 0;
void ReceiveA(bool x) {
  store.push_back(x);
  cnt++;
  if (now == 1) {
    if (cnt == 9) {
      auto [who, cur] = get_best();
      int val = 0;
      for (int j = 0; j < 9; j++) {
        if (store[j]) val |= (1 << j);
      }
      store.clear();
      cnt = 0;
      if (val == 511) {
        send_node(who);
        dist[who] = cur;
        cur_dist = cur;
        done[who] = true;
        if (rem()) {
          auto [w, cc] = get_best();
          send_weight(cc - cur_dist);
          now = 1;
        }
      } else {
        cur_dist += val;
        now = 0;
      }
    }
  } else {
    if (cnt == 11) {
      int who = 0;
      for (int j = 0; j < 11; j++) {
        if (store[j]) who |= (1 << j);
      }
      store.clear();
      cnt = 0;
      dist[who] = cur_dist;
      done[who] = true;
      now = 1;
      if (rem()) {
        auto [w, cc] = get_best();
        send_weight(cc - cur_dist);
      }
    }
  }
}

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

#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2005;
const int inf = mxN * 500;
vector<pair<int, int>> add[mxN];
int nn;
int distt[mxN];
int cur_distt = 0;
bool donee[mxN];
void send_nodee(int u) {
  for (int i = 0; i < 11; i++) {
    SendB(u >> i & 1);
  }
}
void send_weightt(int w) {
  w = min(w, 511);
  for (int i = 0; i < 9; i++) {
    SendB(w >> i & 1);
  }
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
  nn = N;
  for (int i = 0; i < B; i++) {
    add[S[i]].push_back({T[i], D[i]});
    add[T[i]].push_back({S[i], D[i]});
  }
  for (int i = 0; i < nn; i++) {
    distt[i] = inf;
  }
  distt[0] = 0;
  donee[0] = 1;
}
pair<int, int> get_bestt() {
  int who = -1, cur = inf;
  for (int i = 0; i < nn; i++) {
    if (!donee[i]) continue;
    for (auto [j, w] : add[i]) {
      if (donee[j]) continue;
      if (distt[i] + w < cur) {
        cur = distt[i] + w;
        who = j;
      }
    }
  }
  return {who, cur};
}
int noww = 1;
vector<int> storee;
int cntt = 0;
void ReceiveB(bool y) {
  cntt++;
  storee.push_back(y);
  if (noww) {
    if (cntt == 9) {
      auto [who, cur] = get_bestt();
      int val = 0;
      for (int j = 0; j < 9; j++) {
        if (storee[j]) val |= (1 << j);
      }
      storee.clear();
      cntt = 0;
      if (val <= cur - cur_distt) {
        send_weightt(511);
        cur_distt += val;
        noww = 0;
      } else {
        send_weightt(cur - cur_distt);
        send_nodee(who);
        cur_distt = cur;
        distt[who] = cur;
        donee[who] = true;
        noww = 1;
      }
    }
  } else {
    if (cntt == 11) {
      int who = 0;
      for (int j = 0; j < 11; j++) {
        if (storee[j]) who |= (1 << j);
      }
      storee.clear();
      cntt = 0;
      distt[who] = cur_distt;
      donee[who] = true;
      noww = 1;
    }
  }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 1052 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 378 ms 1044 KB Output is correct
4 Correct 923 ms 10368 KB Output is correct
5 Correct 13 ms 920 KB Output is correct
6 Correct 621 ms 2456 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 370 ms 1124 KB Output is correct
3 Correct 401 ms 936 KB Output is correct
4 Execution timed out 3000 ms 27180 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 860 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 354 ms 1048 KB Output is correct
4 Correct 326 ms 876 KB Output is correct
5 Correct 359 ms 876 KB Output is correct
6 Correct 358 ms 868 KB Output is correct
7 Correct 363 ms 876 KB Output is correct
8 Correct 357 ms 800 KB Output is correct
9 Correct 360 ms 792 KB Output is correct
10 Correct 383 ms 1172 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 820 KB Output is correct
2 Correct 133 ms 788 KB Output is correct
3 Correct 742 ms 13584 KB Output is correct
4 Correct 140 ms 664 KB Output is correct
5 Correct 642 ms 10196 KB Output is correct
6 Correct 177 ms 916 KB Output is correct
7 Correct 148 ms 664 KB Output is correct
8 Correct 155 ms 664 KB Output is correct
9 Correct 2675 ms 18212 KB Output is correct
10 Correct 1446 ms 18480 KB Output is correct
11 Execution timed out 3000 ms 35808 KB
12 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 820 KB Output is correct
2 Correct 133 ms 788 KB Output is correct
3 Correct 742 ms 13584 KB Output is correct
4 Correct 140 ms 664 KB Output is correct
5 Correct 642 ms 10196 KB Output is correct
6 Correct 177 ms 916 KB Output is correct
7 Correct 148 ms 664 KB Output is correct
8 Correct 155 ms 664 KB Output is correct
9 Correct 2675 ms 18212 KB Output is correct
10 Correct 1446 ms 18480 KB Output is correct
11 Execution timed out 3000 ms 35808 KB
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 820 KB Output is correct
2 Correct 133 ms 788 KB Output is correct
3 Correct 742 ms 13584 KB Output is correct
4 Correct 140 ms 664 KB Output is correct
5 Correct 642 ms 10196 KB Output is correct
6 Correct 177 ms 916 KB Output is correct
7 Correct 148 ms 664 KB Output is correct
8 Correct 155 ms 664 KB Output is correct
9 Correct 2675 ms 18212 KB Output is correct
10 Correct 1446 ms 18480 KB Output is correct
11 Execution timed out 3000 ms 35808 KB
12 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 1052 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 378 ms 1044 KB Output is correct
4 Correct 923 ms 10368 KB Output is correct
5 Correct 13 ms 920 KB Output is correct
6 Correct 621 ms 2456 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 370 ms 1124 KB Output is correct
9 Correct 401 ms 936 KB Output is correct
10 Execution timed out 3000 ms 27180 KB Time limit exceeded
11 Halted 0 ms 0 KB -