Submission #42914

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

coprobber

#include <bits/stdc++.h>

const int MAX_N = 500;

// modify the following functions
// you can define global variables and functions

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

int Pu = 0;

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

int start(int N, bool A[MAX_N][MAX_N]) {
   for(int p = 0; p < N; p++) {
      for(int r = 0; r < N; r++) {
         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);
            }
            if(A[r][v]) {
               G[0][p][r].emplace_back(1, p, v);
            }
         }
      }
   }
   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;
}

/*
// 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;
    }
}
*/

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