oj.uz

답안 #901153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901153 2024-01-09T07:36:11 Z nguyentunglam Two Transportations (JOI19_transportations) C++17
38 / 100
 479 ms 35796 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 pre;
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) {
  assert(cost - pre <= 500);
  pre = cost;
  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));
    ::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, pre;
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;
  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:89:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   89 |     for(int i = M1; i < M1 + M2; i++) if (bitA[i]) u |= (1 << i - M1);
      |                                                               ~~^~~~

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 664 KB Output is correct
2 Correct 319 ms 800 KB Output is correct
3 Correct 393 ms 13448 KB Output is correct
4 Correct 327 ms 664 KB Output is correct
5 Correct 362 ms 10060 KB Output is correct
6 Correct 282 ms 664 KB Output is correct
7 Correct 329 ms 664 KB Output is correct
8 Correct 278 ms 664 KB Output is correct
9 Correct 450 ms 18256 KB Output is correct
10 Correct 465 ms 18480 KB Output is correct
11 Correct 443 ms 35796 KB Output is correct
12 Correct 479 ms 30812 KB Output is correct
13 Correct 332 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 664 KB Output is correct
2 Correct 319 ms 800 KB Output is correct
3 Correct 393 ms 13448 KB Output is correct
4 Correct 327 ms 664 KB Output is correct
5 Correct 362 ms 10060 KB Output is correct
6 Correct 282 ms 664 KB Output is correct
7 Correct 329 ms 664 KB Output is correct
8 Correct 278 ms 664 KB Output is correct
9 Correct 450 ms 18256 KB Output is correct
10 Correct 465 ms 18480 KB Output is correct
11 Correct 443 ms 35796 KB Output is correct
12 Correct 479 ms 30812 KB Output is correct
13 Correct 332 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Runtime error 153 ms 500 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 664 KB Output is correct
2 Correct 319 ms 800 KB Output is correct
3 Correct 393 ms 13448 KB Output is correct
4 Correct 327 ms 664 KB Output is correct
5 Correct 362 ms 10060 KB Output is correct
6 Correct 282 ms 664 KB Output is correct
7 Correct 329 ms 664 KB Output is correct
8 Correct 278 ms 664 KB Output is correct
9 Correct 450 ms 18256 KB Output is correct
10 Correct 465 ms 18480 KB Output is correct
11 Correct 443 ms 35796 KB Output is correct
12 Correct 479 ms 30812 KB Output is correct
13 Correct 332 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Runtime error 153 ms 500 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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