Submission #42929

#	Time	Username	Problem	Language	Result	Execution time	Memory
42929		ruhanhabib39	Cop and Robber (BOI14_coprobber)	C++14	60 / 100	347 ms	262144 KiB

coprobber

#include <bits/stdc++.h>

const int MAX_N = 500;

int nx[2][MAX_N][MAX_N];
std::vector<int> G[2][MAX_N][MAX_N];
int cc[2][MAX_N][MAX_N];

int Pu = 0;

struct Dat {
   int x;
   Dat(int m, int p, int r) {
      x = m; // [0, 0]
      x |= p << 1; // [1, 9]
      x |= r << 10; // [10, 18]
   }
   int getM() const {
      return x & 1;
   }
   int getR() const {
      return x >> 10;
   }
   int getP() const {
      return (x >> 1) & 511; // 511 = 2**9 - 1
   }
   void set(int& m, int& p, int& r) const {
      m = getM();
      p = getP();
      r = getR();
   }
};

void bfs(int N, bool A[MAX_N][MAX_N]) {
   std::memset(nx, -1, sizeof nx);
   for(int r = 0; r < N; r++) {
      int deg = std::count(A[r], A[r] + N, true);
      for(int p = 0; p < N; p++) {
         cc[0][p][r] = 1;
         cc[1][p][r] = deg;
      }
   }
   std::queue<Dat> q;
   for(int p = 0; p < N; p++) {
      cc[0][p][p] = cc[1][p][p] = 0;
      q.push(Dat(0, p, p)); q.push(Dat(1, p, p));
      nx[0][p][p] = nx[1][p][p] = p;
   }
   while(!q.empty()) {
      int m, p, r; q.front().set(m, p, r);
      //if(m == 0) std::cerr << (m == 0 ? 'P' : 'R')  << " " << p << " " << r << "\n";
      q.pop();
      if(m == 0) {
         for(int v : G[m][p][r]) {
            int m1 = 1, p1 = p, r1 = v;
            cc[m1][p1][r1]--;
            if(cc[m1][p1][r1] == 0) {
               nx[m1][p1][r1] = r;
               q.push(Dat(m1, p1, r1));
            }
         }
      } else {
         for(int v : G[m][p][r]) {
            int m1 = 0, p1 = v, r1 = r;
            cc[m1][p1][r1]--;
            if(cc[m1][p1][r1] == 0) {
               nx[m1][p1][r1] = p;
               q.push(Dat(m1, p1, r1));
            }
         }
      }
   }
}

int add[2][MAX_N], ii = 0, jj = 0;

int start(int N, bool A[MAX_N][MAX_N]) {
   for(int p = 0; p < N; p++) {
      for(int r = 0; r < N; r++) {
         ii = jj = 0;
         add[1][ii++] = p;
         //G[1][p][r].emplace_back(0, p, r);
         for(int v = 0; v < N; v++) {
            if(A[p][v]) {
               //G[1][p][r].emplace_back(0, v, r);
               add[1][ii++] = v;
            }
            if(A[r][v]) {
               //G[0][p][r].emplace_back(1, p, v);
               add[0][jj++] = v;
            }
         }
         G[0][p][r] = std::vector<int>(add[0], add[0]+jj);
         G[1][p][r] = std::vector<int>(add[1], add[1]+ii);
      }
   }
   bfs(N, A);
   for(int r = 0; r < N; r++) {
      if(nx[0][0][r] == -1 || cc[0][0][r] > 0) {
         //std::cerr << "bad " << r << std::endl;
         return -1;
      }
   }
   return Pu = 0;
}

int nextMove(int R) {
   Pu = nx[0][Pu][R];
   return Pu;
}

#ifdef DEBUG
// don't modify the main function
int main() {
    int N;
    std::cin >> N;
    bool A[MAX_N][MAX_N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            std::cin >> A[i][j];
        }
    }
    int P = start(N,A);
    std::cout << P << std::endl;
    //std::exit(0);
    int R;
    std::cin >> R;
    while (true) {
        if (P == R) break;
        P = nextMove(R);
        std::cout << P << std::endl;
        if (P == R) break;
        std::cin >> R;
    }
}
#endif

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40