oj.uz

Submission #200363

# Submission time Handle Problem Language Result Execution time Memory
200363 2020-02-06T11:52:46 Z EntityIT Two Transportations (JOI19_transportations) C++14
100 / 100
 1862 ms 85480 KB 
#include "Azer.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

namespace A {
  const int inf = 1e9;

  int n, a;
  vector<vector<pair<int, int> > > gr;

  int mxD;
  vector<int> d;
  int cntDone = 0;
  vector<bool> done;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

  pair<int, int> cur{};
  int dest = 9;

  void ins(int u) { pq.emplace(d[u], u); }
  int get() {
    if (!sz(pq) ) return -1;

    int ret = pq.top().second; pq.pop();
    done[ret] = true;
    mxD = d[ret];
    ++cntDone;
    while (sz(pq) && done[pq.top().second]) pq.pop();
    return ret;
  }

  int relaxingD;

  void relax(int u) {
    for (auto e : gr[u]) {
      int v = e.first, w = e.second;

      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        ins(v);
      }
    }

//    cerr << "A: ";
//    for (int i : d) cerr << i << ' ';
//    cerr << '\n';
  }

  void send(int val, int len) {
//    cerr << "A send: " << len << ' ' << val << '\n';
    for (int i = 0; i < len; ++i) SendA( (val >> i) & 1);
  }
}

void InitA(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
  A::n = N;
  A::a = A;
  A::gr.assign(A::n, {} );
  for (int i = 0; i < A::a; ++i) {
    A::gr[ U[i] ].emplace_back(V[i], C[i]);
    A::gr[ V[i] ].emplace_back(U[i], C[i]);
  }

  A::mxD = 0;
  A::d.assign(A::n, A::inf); A::d[0] = 0;
  A::done.assign(A::n, false);
  A::ins(0);

  A::send(0, 9);
}

void ReceiveA(bool x) {
  A::cur.second |= (x << (A::cur.first++) );

  if (A::cur.first < A::dest) return ;

//  cerr << "A receive: " << A::cur.first << ' ' << A::cur.second << '\n';

  if (A::dest == 9) {
    if (A::cur.second == (1 << 9) - 1) {
      int u = A::get();
      A::send(u, 11);
      A::relax(u);

      if (A::cntDone == A::n) return ;

      if (sz(A::pq) ) {
        int tmp = A::pq.top().first - A::mxD;
        A::send(tmp, 9);
      }
      else A::send( (1 << 9) - 1, 9);
    }
    else {
      A::relaxingD = A::cur.second;
      A::dest = 11;
    }
  }
  else {
    int u = A::cur.second;
    A::mxD = A::d[u] = A::mxD + A::relaxingD; A::done[u] = true;
    while (sz(A::pq) && A::done[A::pq.top().second]) A::pq.pop();

    A::relax(u);

    ++A::cntDone;
    if (A::cntDone == A::n) return;

    if (sz(A::pq) ) {
      int tmp = A::pq.top().first - A::mxD;
      A::send(tmp, 9);
    }
    else A::send( (1 << 9) - 1, 9);
    A::dest = 9;
  }

  A::cur = {};
}

vector<int> Answer() { return A::d; }

#include "Baijan.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

namespace B{
  const int inf = 1e9;

  int n, b;
  vector<vector<pair<int, int> > > gr;

  int mxD;
  vector<int> d;
  int cntDone = 0;
  vector<bool> done;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

  pair<int, int> cur{};
  int dest = 9;

  void ins(int u) { pq.emplace(d[u], u); }
  int get() {
    if (!sz(pq) ) return -1;

    int ret = pq.top().second; pq.pop();
    done[ret] = true;
    mxD = d[ret];
    ++cntDone;
    while (sz(pq) && done[pq.top().second]) pq.pop();
    return ret;
  }

  int relaxingD;

  void relax(int u) {
    for (auto e : gr[u]) {
      int v = e.first, w = e.second;

      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        ins(v);
      }
    }

//    cerr << "B: ";
//    for (int i : d) cerr << i << ' ';
//    cerr << '\n';
  }

  void send(int val, int len) {
//    cerr << "B send: " << len << ' ' << val << '\n';
    for (int i = 0; i < len; ++i) SendB( (val >> i) & 1);
  }
}

void InitB(int N, int B, vector<int> S, vector<int> T,
           vector<int> D) {
  B::n = N;
  B::b = B;
  B::gr.assign(B::n, {} );
  for (int i = 0; i < B::b; ++i) {
    B::gr[ S[i] ].emplace_back(T[i], D[i]);
    B::gr[ T[i] ].emplace_back(S[i], D[i]);
  }

  B::mxD = 0;
  B::d.assign(B::n, B::inf); B::d[0] = 0;
  B::done.assign(B::n, false);
  B::ins(0);
}

void ReceiveB(bool y) {
  B::cur.second |= (y << (B::cur.first++) );

  if (B::cur.first < B::dest) return ;

//  cerr << "B receive: " << B::cur.first << ' ' << B::cur.second << '\n';

  if (B::dest == 9) {
    int tmp = (sz(B::pq) ? B::pq.top().first - B::mxD : (1 << 9) - 2);

    if (tmp < B::cur.second) {
      int u = B::get();
      B::relax(u);

      B::send(tmp, 9);
      B::send(u, 11);
    }
    else {
      B::relaxingD = B::cur.second;

      B::send( (1 << 9) - 1, 9);

      B::dest = 11;
    }
  }
  else {
    int u = B::cur.second;
    B::mxD = B::d[u] = B::relaxingD + B::mxD; B::done[u] = true;
    while (sz(B::pq) && B::done[B::pq.top().second]) B::pq.pop();

    B::relax(u);

    ++B::cntDone;
    if (B::cntDone == B::n) return;

    B::dest = 9;
  }

  B::cur = {};
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 2016 KB Output is correct
2 Correct 18 ms 1248 KB Output is correct
3 Correct 888 ms 2048 KB Output is correct
4 Correct 1186 ms 20456 KB Output is correct
5 Correct 68 ms 1504 KB Output is correct
6 Correct 956 ms 4776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1248 KB Output is correct
2 Correct 950 ms 1824 KB Output is correct
3 Correct 1058 ms 2016 KB Output is correct
4 Correct 1476 ms 55336 KB Output is correct
5 Correct 1392 ms 48352 KB Output is correct
6 Correct 256 ms 1504 KB Output is correct
7 Correct 1442 ms 48680 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 1760 KB Output is correct
2 Correct 18 ms 1000 KB Output is correct
3 Correct 1044 ms 1864 KB Output is correct
4 Correct 924 ms 1504 KB Output is correct
5 Correct 1010 ms 1760 KB Output is correct
6 Correct 1014 ms 1504 KB Output is correct
7 Correct 972 ms 1760 KB Output is correct
8 Correct 900 ms 1760 KB Output is correct
9 Correct 981 ms 1512 KB Output is correct
10 Correct 956 ms 2016 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1248 KB Output is correct
2 Correct 458 ms 1248 KB Output is correct
3 Correct 666 ms 23544 KB Output is correct
4 Correct 458 ms 1504 KB Output is correct
5 Correct 620 ms 17384 KB Output is correct
6 Correct 486 ms 1504 KB Output is correct
7 Correct 452 ms 2016 KB Output is correct
8 Correct 478 ms 1760 KB Output is correct
9 Correct 784 ms 36000 KB Output is correct
10 Correct 782 ms 36064 KB Output is correct
11 Correct 1160 ms 61128 KB Output is correct
12 Correct 936 ms 53848 KB Output is correct
13 Correct 502 ms 1504 KB Output is correct
14 Correct 18 ms 1248 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1248 KB Output is correct
2 Correct 458 ms 1248 KB Output is correct
3 Correct 666 ms 23544 KB Output is correct
4 Correct 458 ms 1504 KB Output is correct
5 Correct 620 ms 17384 KB Output is correct
6 Correct 486 ms 1504 KB Output is correct
7 Correct 452 ms 2016 KB Output is correct
8 Correct 478 ms 1760 KB Output is correct
9 Correct 784 ms 36000 KB Output is correct
10 Correct 782 ms 36064 KB Output is correct
11 Correct 1160 ms 61128 KB Output is correct
12 Correct 936 ms 53848 KB Output is correct
13 Correct 502 ms 1504 KB Output is correct
14 Correct 18 ms 1248 KB Output is correct
15 Correct 548 ms 1504 KB Output is correct
16 Correct 568 ms 1248 KB Output is correct
17 Correct 582 ms 1504 KB Output is correct
18 Correct 730 ms 17864 KB Output is correct
19 Correct 568 ms 1760 KB Output is correct
20 Correct 722 ms 18184 KB Output is correct
21 Correct 552 ms 1504 KB Output is correct
22 Correct 579 ms 1760 KB Output is correct
23 Correct 954 ms 44000 KB Output is correct
24 Correct 956 ms 43872 KB Output is correct
25 Correct 1438 ms 75192 KB Output is correct
26 Correct 1154 ms 64200 KB Output is correct
27 Correct 542 ms 1760 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1248 KB Output is correct
2 Correct 458 ms 1248 KB Output is correct
3 Correct 666 ms 23544 KB Output is correct
4 Correct 458 ms 1504 KB Output is correct
5 Correct 620 ms 17384 KB Output is correct
6 Correct 486 ms 1504 KB Output is correct
7 Correct 452 ms 2016 KB Output is correct
8 Correct 478 ms 1760 KB Output is correct
9 Correct 784 ms 36000 KB Output is correct
10 Correct 782 ms 36064 KB Output is correct
11 Correct 1160 ms 61128 KB Output is correct
12 Correct 936 ms 53848 KB Output is correct
13 Correct 502 ms 1504 KB Output is correct
14 Correct 18 ms 1248 KB Output is correct
15 Correct 548 ms 1504 KB Output is correct
16 Correct 568 ms 1248 KB Output is correct
17 Correct 582 ms 1504 KB Output is correct
18 Correct 730 ms 17864 KB Output is correct
19 Correct 568 ms 1760 KB Output is correct
20 Correct 722 ms 18184 KB Output is correct
21 Correct 552 ms 1504 KB Output is correct
22 Correct 579 ms 1760 KB Output is correct
23 Correct 954 ms 44000 KB Output is correct
24 Correct 956 ms 43872 KB Output is correct
25 Correct 1438 ms 75192 KB Output is correct
26 Correct 1154 ms 64200 KB Output is correct
27 Correct 542 ms 1760 KB Output is correct
28 Correct 736 ms 1504 KB Output is correct
29 Correct 708 ms 1248 KB Output is correct
30 Correct 1142 ms 41952 KB Output is correct
31 Correct 759 ms 1512 KB Output is correct
32 Correct 1072 ms 37672 KB Output is correct
33 Correct 734 ms 1760 KB Output is correct
34 Correct 710 ms 1760 KB Output is correct
35 Correct 710 ms 1760 KB Output is correct
36 Correct 1134 ms 49456 KB Output is correct
37 Correct 1070 ms 49448 KB Output is correct
38 Correct 1620 ms 85480 KB Output is correct
39 Correct 1348 ms 78432 KB Output is correct
40 Correct 688 ms 1760 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 2016 KB Output is correct
2 Correct 18 ms 1248 KB Output is correct
3 Correct 888 ms 2048 KB Output is correct
4 Correct 1186 ms 20456 KB Output is correct
5 Correct 68 ms 1504 KB Output is correct
6 Correct 956 ms 4776 KB Output is correct
7 Correct 18 ms 1248 KB Output is correct
8 Correct 950 ms 1824 KB Output is correct
9 Correct 1058 ms 2016 KB Output is correct
10 Correct 1476 ms 55336 KB Output is correct
11 Correct 1392 ms 48352 KB Output is correct
12 Correct 256 ms 1504 KB Output is correct
13 Correct 1442 ms 48680 KB Output is correct
14 Correct 994 ms 1760 KB Output is correct
15 Correct 18 ms 1000 KB Output is correct
16 Correct 1044 ms 1864 KB Output is correct
17 Correct 924 ms 1504 KB Output is correct
18 Correct 1010 ms 1760 KB Output is correct
19 Correct 1014 ms 1504 KB Output is correct
20 Correct 972 ms 1760 KB Output is correct
21 Correct 900 ms 1760 KB Output is correct
22 Correct 981 ms 1512 KB Output is correct
23 Correct 956 ms 2016 KB Output is correct
24 Correct 482 ms 1248 KB Output is correct
25 Correct 458 ms 1248 KB Output is correct
26 Correct 666 ms 23544 KB Output is correct
27 Correct 458 ms 1504 KB Output is correct
28 Correct 620 ms 17384 KB Output is correct
29 Correct 486 ms 1504 KB Output is correct
30 Correct 452 ms 2016 KB Output is correct
31 Correct 478 ms 1760 KB Output is correct
32 Correct 784 ms 36000 KB Output is correct
33 Correct 782 ms 36064 KB Output is correct
34 Correct 1160 ms 61128 KB Output is correct
35 Correct 936 ms 53848 KB Output is correct
36 Correct 502 ms 1504 KB Output is correct
37 Correct 18 ms 1248 KB Output is correct
38 Correct 548 ms 1504 KB Output is correct
39 Correct 568 ms 1248 KB Output is correct
40 Correct 582 ms 1504 KB Output is correct
41 Correct 730 ms 17864 KB Output is correct
42 Correct 568 ms 1760 KB Output is correct
43 Correct 722 ms 18184 KB Output is correct
44 Correct 552 ms 1504 KB Output is correct
45 Correct 579 ms 1760 KB Output is correct
46 Correct 954 ms 44000 KB Output is correct
47 Correct 956 ms 43872 KB Output is correct
48 Correct 1438 ms 75192 KB Output is correct
49 Correct 1154 ms 64200 KB Output is correct
50 Correct 542 ms 1760 KB Output is correct
51 Correct 736 ms 1504 KB Output is correct
52 Correct 708 ms 1248 KB Output is correct
53 Correct 1142 ms 41952 KB Output is correct
54 Correct 759 ms 1512 KB Output is correct
55 Correct 1072 ms 37672 KB Output is correct
56 Correct 734 ms 1760 KB Output is correct
57 Correct 710 ms 1760 KB Output is correct
58 Correct 710 ms 1760 KB Output is correct
59 Correct 1134 ms 49456 KB Output is correct
60 Correct 1070 ms 49448 KB Output is correct
61 Correct 1620 ms 85480 KB Output is correct
62 Correct 1348 ms 78432 KB Output is correct
63 Correct 688 ms 1760 KB Output is correct
64 Correct 1060 ms 2136 KB Output is correct
65 Correct 1478 ms 46824 KB Output is correct
66 Correct 1430 ms 41080 KB Output is correct
67 Correct 1026 ms 2344 KB Output is correct
68 Correct 1004 ms 2016 KB Output is correct
69 Correct 1862 ms 83784 KB Output is correct
70 Correct 1792 ms 68056 KB Output is correct
71 Correct 1150 ms 8896 KB Output is correct
72 Correct 1026 ms 2560 KB Output is correct