oj.uz

Submission #122772

# Submission time Handle Problem Language Result Execution time Memory
122772 2019-06-29T09:12:12 Z win11905 Two Transportations (JOI19_transportations) C++14
6 / 100
 831 ms 54904 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

namespace {
  int N, A;
  vector<pii> g[2000];
  vector<int> d;
  int step, val;
  int ns, nid;
  int u, v, w;
  void dijkstra() {
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    Q.emplace(d[0] = 0, 0);
    while(!Q.empty()) {
      auto u = Q.top(); Q.pop();
      if(u.x != d[u.y]) continue;
      for(auto v : g[u.y]) if(d[v.x] > d[u.y] + v.y) 
        Q.emplace(d[v.x] = d[u.y] + v.y, v.x);
    }
  }
}  



void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
  u = v = w = 0;
  SendA(A ? true : false);
  ::N = N, ::A = A;
  d.resize(N, (1 << 20) - 1);
  for(int i = 0; i < A; ++i) {
    g[U[i]].emplace_back(V[i], C[i]);
    g[V[i]].emplace_back(U[i], C[i]);
  }
}

void ReceiveA(bool x) {
  if(step <= 18) {
    if(x) val |= 1 << step;
    step++;
  } else {
    if(A) {
      if(ns < 11) { if(x) u |= 1 << ns; }
      else if(ns < 22) { if(x) v |= 1 << (ns-11); }
      else { if(x) w |= 1 << (ns-22); }
      if(++ns == 32) {
        nid++;
        g[u].emplace_back(v, w), g[v].emplace_back(u, w);
        u = v = w = ns = 0;
      }
      if(nid == val) dijkstra();
    } else {
      if(x) w |= 1 << ns; 
      if(++ns == 20) {
        d[nid++] = w;
        w = ns = 0;
      }
    }
  }
}

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

#include "Baijan.h"
#include <bits/stdc++.h>
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

namespace {
  int N;
  int count;
  int val;
  int step, nid, ns;
  int u, v, w;
  vector<iii> E;
  vector<pii> g[2000];
  vector<int> d;
  void dijkstra() {
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    Q.emplace(d[0] = 0, 0);
    while(!Q.empty()) {
      auto u = Q.top(); Q.pop();
      if(u.x != d[u.y]) continue;
      for(auto v : g[u.y]) if(d[v.x] > d[u.y] + v.y) 
        Q.emplace(d[v.x] = d[u.y] + v.y, v.x);
    }
  }
}  

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
  for(int i = 0; i <= 18; ++i) SendB(B >> i & 1);
  ::N = N;
  d.resize(N, (1<<20) - 1);
  for(int i = 0; i < B; ++i) {
    E.emplace_back(S[i], T[i], D[i]);
    g[S[i]].emplace_back(T[i], D[i]);
    g[T[i]].emplace_back(S[i], D[i]);
  }
}

void ReceiveB(bool y) {
  if(y) {
    for(auto x : E) {
      int u, v, w; tie(u, v, w) = x;
      for(int i = 0; i < 11; ++i) SendB(u >> i & 1);
      for(int i = 0; i < 11; ++i) SendB(v >> i & 1);
      for(int i = 0; i < 10; ++i) SendB(w >> i & 1);
    }
  } else {
    dijkstra();
    for(int i = 0; i < N; ++i) {
      for(int j = 0; j < 20; ++j) SendB(d[i] >> j & 1);
    }
  }
}

Compilation message

Baijan.cpp:14:13: warning: '{anonymous}::w' defined but not used [-Wunused-variable]
   int u, v, w;
             ^
Baijan.cpp:14:10: warning: '{anonymous}::v' defined but not used [-Wunused-variable]
   int u, v, w;
          ^
Baijan.cpp:14:7: warning: '{anonymous}::u' defined but not used [-Wunused-variable]
   int u, v, w;
       ^
Baijan.cpp:13:18: warning: '{anonymous}::ns' defined but not used [-Wunused-variable]
   int step, nid, ns;
                  ^~
Baijan.cpp:13:13: warning: '{anonymous}::nid' defined but not used [-Wunused-variable]
   int step, nid, ns;
             ^~~
Baijan.cpp:13:7: warning: '{anonymous}::step' defined but not used [-Wunused-variable]
   int step, nid, ns;
       ^~~~
Baijan.cpp:12:7: warning: '{anonymous}::val' defined but not used [-Wunused-variable]
   int val;
       ^~~
Baijan.cpp:11:7: warning: '{anonymous}::count' defined but not used [-Wunused-variable]
   int count;
       ^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 1840 KB Output is correct
2 Correct 8 ms 1432 KB Output is correct
3 Correct 626 ms 1856 KB Output is correct
4 Correct 831 ms 25152 KB Output is correct
5 Correct 24 ms 2000 KB Output is correct
6 Correct 822 ms 5528 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1248 KB Output is correct
2 Correct 586 ms 1760 KB Output is correct
3 Correct 576 ms 1640 KB Output is correct
4 Correct 656 ms 54904 KB Output is correct
5 Incorrect 418 ms 48552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 1720 KB Output is correct
2 Correct 4 ms 992 KB Output is correct
3 Correct 712 ms 1520 KB Output is correct
4 Correct 484 ms 2016 KB Output is correct
5 Correct 526 ms 1656 KB Output is correct
6 Correct 580 ms 1496 KB Output is correct
7 Correct 260 ms 1576 KB Output is correct
8 Incorrect 10 ms 896 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1304 KB Output is correct
2 Correct 500 ms 1520 KB Output is correct
3 Incorrect 118 ms 13260 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1304 KB Output is correct
2 Correct 500 ms 1520 KB Output is correct
3 Incorrect 118 ms 13260 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 1304 KB Output is correct
2 Correct 500 ms 1520 KB Output is correct
3 Incorrect 118 ms 13260 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 1840 KB Output is correct
2 Correct 8 ms 1432 KB Output is correct
3 Correct 626 ms 1856 KB Output is correct
4 Correct 831 ms 25152 KB Output is correct
5 Correct 24 ms 2000 KB Output is correct
6 Correct 822 ms 5528 KB Output is correct
7 Correct 8 ms 1248 KB Output is correct
8 Correct 586 ms 1760 KB Output is correct
9 Correct 576 ms 1640 KB Output is correct
10 Correct 656 ms 54904 KB Output is correct
11 Incorrect 418 ms 48552 KB Output isn't correct
12 Halted 0 ms 0 KB -