oj.uz

답안 #900849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900849 2024-01-09T04:36:15 Z nguyentunglam Two Transportations (JOI19_transportations) C++17
0 / 100
 595 ms 35792 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();

  ::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 183 ms 468 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 824 KB Output is correct
2 Correct 248 ms 796 KB Output is correct
3 Correct 351 ms 13440 KB Output is correct
4 Correct 319 ms 664 KB Output is correct
5 Correct 354 ms 10196 KB Output is correct
6 Correct 328 ms 836 KB Output is correct
7 Correct 301 ms 664 KB Output is correct
8 Correct 254 ms 664 KB Output is correct
9 Correct 357 ms 18220 KB Output is correct
10 Correct 396 ms 18468 KB Output is correct
11 Correct 595 ms 35792 KB Output is correct
12 Correct 410 ms 30772 KB Output is correct
13 Correct 285 ms 844 KB Output is correct
14 Runtime error 1 ms 476 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 824 KB Output is correct
2 Correct 248 ms 796 KB Output is correct
3 Correct 351 ms 13440 KB Output is correct
4 Correct 319 ms 664 KB Output is correct
5 Correct 354 ms 10196 KB Output is correct
6 Correct 328 ms 836 KB Output is correct
7 Correct 301 ms 664 KB Output is correct
8 Correct 254 ms 664 KB Output is correct
9 Correct 357 ms 18220 KB Output is correct
10 Correct 396 ms 18468 KB Output is correct
11 Correct 595 ms 35792 KB Output is correct
12 Correct 410 ms 30772 KB Output is correct
13 Correct 285 ms 844 KB Output is correct
14 Runtime error 1 ms 476 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 824 KB Output is correct
2 Correct 248 ms 796 KB Output is correct
3 Correct 351 ms 13440 KB Output is correct
4 Correct 319 ms 664 KB Output is correct
5 Correct 354 ms 10196 KB Output is correct
6 Correct 328 ms 836 KB Output is correct
7 Correct 301 ms 664 KB Output is correct
8 Correct 254 ms 664 KB Output is correct
9 Correct 357 ms 18220 KB Output is correct
10 Correct 396 ms 18468 KB Output is correct
11 Correct 595 ms 35792 KB Output is correct
12 Correct 410 ms 30772 KB Output is correct
13 Correct 285 ms 844 KB Output is correct
14 Runtime error 1 ms 476 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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