oj.uz

답안 #900856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900856 2024-01-09T04:38:57 Z nguyentunglam Two Transportations (JOI19_transportations) C++17
38 / 100
 532 ms 35884 KB 
#include "Azer.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

const int M1 = 20, M2 = 11;

namespace {

const int N = 2e3 + 10;
int n;
int cnt;
int d[N];
bool mark[N];
vector<pair<int, int> > adj[N];

#define ii pair<int, int>
priority_queue<ii, vector<ii>, greater<ii> > q;

void init () {
  mark[0] = 1;
  d[0] = 0;
  for(int i = 1; i < n; i++) mark[i] = 0, d[i] = (1 << 30) - 1;
  for(auto &it : adj[0]) {
    int v, w; tie(v, w) = it;
    q.push({d[v] = w, v});
  }
}

void add_edge (int u, int v, int w) {
  adj[u].emplace_back(v, w);
  adj[v].emplace_back(u, w);
}

pair<int, int> nxt;

void add () {
  while (!q.empty() && mark[q.top().second]) q.pop();
  if (q.empty()) {
    nxt = make_pair((1 << 20) - 1, (1 << 11) - 1);
    for(int i = 0; i < M1 + M2; i++) SendA(1);
    return;
  }
  int cost, u; tie(cost, u) = q.top();
  nxt = make_pair(cost, u);
  for(int i = 0; i < M1; i++) SendA(cost >> i & 1);
  for(int i = 0; i < M2; i++) SendA(u >> i & 1);
}


void calc (int cost, int u) {
  mark[u] = 1;
  d[u] = cost;
  if (cost > 1e6) assert(0);
  for(auto &it : adj[u]) {
    int v, w; tie(v, w) = it;
    if (d[v] > d[u] + w) q.push({d[v] = d[u] + w, v});
  }
}
}  // 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++) adj[i].clear();
  for (int i = 0; i < A; ++i) {
    ::add_edge(U[i], V[i], C[i]);
  }

  ::init();

  if (N > 1) ::add();

  Answer();
}

bool bitA[100];

int cntA;

void ReceiveA(bool x) {
  bitA[cntA++] = x;
  if (cntA == M1 + M2) {
    int cost = 0, u = 0;
    for(int i = 0; i < M1; i++) if (bitA[i]) cost |= (1 << i);
    for(int i = M1; i < M1 + M2; i++) if (bitA[i]) u |= (1 << i - M1);
    nxt = min(nxt, make_pair(cost, u));
//    if (nxt.first > 1e6) {
//      cout << nxt.first << endl;
//      exit(0);
//    }
//    cout << nxt.first << " " << nxt.second << endl;
    ::calc(nxt.first, nxt.second);
    cntA = 0;
    if (++::cnt < n - 1) ::add();
  }
}

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

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

const int M1 = 20, M2 = 11;

namespace {

const int N = 2e3 + 10;
int n;
int cnt;
int d[N];
bool mark[N];
vector<pair<int, int> > adj[N];

#define ii pair<int, int>
priority_queue<ii, vector<ii>, greater<ii> > q;

void init () {
  mark[0] = 1;
  for(int i = 1; i < n; i++) mark[i] = 0, d[i] = (1 << 20) - 1;
  for(auto &it : adj[0]) {
    int v, w; tie(v, w) = it;
    q.push({d[v] = w, v});
  }
}

void add_edge (int u, int v, int w) {
  adj[u].emplace_back(v, w);
  adj[v].emplace_back(u, w);
}

pair<int, int> nxt;

void add () {
  while (!q.empty() && mark[q.top().second]) q.pop();
  if (q.empty()) {
    for(int i = 0; i < M1 + M2; i++) SendB(1);
    nxt = make_pair((1 << 20) - 1, (1 << 11) - 1);
    return;
  }
  int cost, u; tie(cost, u) = q.top();
  nxt = make_pair(cost, u);
  for(int i = 0; i < M1; i++) SendB(cost >> i & 1);
  for(int i = 0; i < M2; i++) SendB(u >> i & 1);
}


void calc (int cost, int u) {
  mark[u] = 1;
  d[u] = cost;
//  if (cost > 1e6) return;
  for(auto &it : adj[u]) {
    int v, w; tie(v, w) = it;
    if (d[v] > d[u] + w) q.push({d[v] = d[u] + w, v});
  }
}

}  // 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++) adj[i].clear();
  for(int i = 0; i < B; i++) {
    ::add_edge(S[i], T[i], D[i]);
  }
  ::init();
}

bool bitB[100];

int cntB;

void ReceiveB(bool y) {
  bitB[cntB++] = y;
  if (cntB == M1 + M2) {
    int cost = 0, u = 0;
    for(int i = 0; i < M1; i++) if (bitB[i]) cost |= (1 << i);
    for(int i = M1; i < M1 + M2; i++) if (bitB[i]) u |= (1 << i - M1);
    ::add();
    nxt = min(nxt, make_pair(cost, u));
    calc(nxt.first, nxt.second);
    cntB = 0;
  }
}

Compilation message

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:86:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   86 |     for(int i = M1; i < M1 + M2; i++) if (bitA[i]) u |= (1 << i - M1);
      |                                                               ~~^~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:81:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   81 |     for(int i = M1; i < M1 + M2; i++) if (bitB[i]) u |= (1 << i - M1);
      |                                                               ~~^~~~
Baijan.cpp: At global scope:
Baijan.cpp:12:5: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
   12 | int cnt;
      |     ^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 118 ms 464 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 664 KB Output is correct
2 Runtime error 146 ms 556 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 536 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 824 KB Output is correct
2 Correct 316 ms 800 KB Output is correct
3 Correct 357 ms 13364 KB Output is correct
4 Correct 356 ms 664 KB Output is correct
5 Correct 393 ms 10056 KB Output is correct
6 Correct 269 ms 664 KB Output is correct
7 Correct 278 ms 664 KB Output is correct
8 Correct 268 ms 664 KB Output is correct
9 Correct 469 ms 18216 KB Output is correct
10 Correct 401 ms 18468 KB Output is correct
11 Correct 532 ms 35884 KB Output is correct
12 Correct 450 ms 30772 KB Output is correct
13 Correct 343 ms 664 KB Output is correct
14 Correct 0 ms 920 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 824 KB Output is correct
2 Correct 316 ms 800 KB Output is correct
3 Correct 357 ms 13364 KB Output is correct
4 Correct 356 ms 664 KB Output is correct
5 Correct 393 ms 10056 KB Output is correct
6 Correct 269 ms 664 KB Output is correct
7 Correct 278 ms 664 KB Output is correct
8 Correct 268 ms 664 KB Output is correct
9 Correct 469 ms 18216 KB Output is correct
10 Correct 401 ms 18468 KB Output is correct
11 Correct 532 ms 35884 KB Output is correct
12 Correct 450 ms 30772 KB Output is correct
13 Correct 343 ms 664 KB Output is correct
14 Correct 0 ms 920 KB Output is correct
15 Runtime error 170 ms 500 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 824 KB Output is correct
2 Correct 316 ms 800 KB Output is correct
3 Correct 357 ms 13364 KB Output is correct
4 Correct 356 ms 664 KB Output is correct
5 Correct 393 ms 10056 KB Output is correct
6 Correct 269 ms 664 KB Output is correct
7 Correct 278 ms 664 KB Output is correct
8 Correct 268 ms 664 KB Output is correct
9 Correct 469 ms 18216 KB Output is correct
10 Correct 401 ms 18468 KB Output is correct
11 Correct 532 ms 35884 KB Output is correct
12 Correct 450 ms 30772 KB Output is correct
13 Correct 343 ms 664 KB Output is correct
14 Correct 0 ms 920 KB Output is correct
15 Runtime error 170 ms 500 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 118 ms 464 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -