제출 #42932

#제출 시각아이디문제언어결과실행 시간메모리
42932ruhanhabib39경찰관과 강도 (BOI14_coprobber)C++14
100 / 100
616 ms18988 KiB
#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 = 0; v < N; v++) { if(!A[r][v] || cc[1][p][v] == 0) continue; const 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 = 0; v < N; v++) { if(!A[p][v] || cc[0][v][r] == 0) continue; const int m1 = 0, p1 = v, r1 = r; cc[m1][p1][r1] = 0; nx[m1][p1][r1] = p; q.push(Dat(m1, p1, r1)); } if(cc[0][p][r]) { cc[0][p][r] = 0; nx[0][p][r] = p; q.push(Dat(0, p, r)); } } } } int add[2][MAX_N], ii = 0, jj = 0; int start(int N, bool A[MAX_N][MAX_N]) { 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; } //#define DEBUG #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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...