Submission #584594

#	Time	Username	Problem	Language	Result	Execution time	Memory
584594		MohammadAghil	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	1428 ms	15840 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss secounf 
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 5e2+1, inf = ll(1e9)+5;


struct state{
     int u, v, id;
     bool nb;
     state(){}
     state(int u, int v, int nb): u(u), v(v), nb(nb){ 
          id = (u*maxn + v)<<1|nb; 
     }
     state(int id): id(id){
          nb = id&1, id >>= 1;
          v = id%maxn, u = id/maxn;
     }
};

int n, cnt[maxn*maxn];
state SS[maxn*maxn*2];
int SID[maxn][maxn][2], SIDd[maxn][maxn];
// vector<int> adjr[maxn*maxn*2];
// bool win[maxn*maxn*2];
bitset<maxn*maxn*2> win;
bool B[maxn][maxn];
int nxt[maxn*maxn], out[maxn*maxn];

#define MAX_N 500


vector<int> adjr(state a){
     vector<int> res; res.reserve(n+1);
     if(a.nb){
          rep(i,0,n) if(B[i][a.u]) res.pb(SID[i][a.v][0]);
          res.pb(a.id^1);
          if(a.v == n) res.pb(SID[n][n][0]);
     }else{
          rep(i,0,n) if(B[i][a.v]) res.pb(SID[a.u][i][1]);
          res.pb(SID[a.u][n][1]);
     }
     return res;
}

void calc(){
     vector<int> winners;
     rep(i,0,n) rep(t,0,2) winners.pb(SID[i][i][t]), win[winners.back()] = true;
     int id = 0;
     while(sz(winners)){
          int r = winners.back(); winners.pop_back();
          state R = SS[r];
          // cout << r << endl;
          for(int c: adjr(R)){
               if(win[c]) continue;
               id = c, c>>=1;
               if(id&1){
                    cnt[c]++;
                    if(cnt[c] == out[c]) {
                         winners.pb(id);
                         win[winners.back()] = true;
                    }
               }else winners.pb(id), nxt[c] = R.u, win[winners.back()] = true;
          }
     }
}

int u, v;

int nextMove(int r){
     v = r, u = nxt[SIDd[u][v]];
     return u;
}

int start(int n, bool A[MAX_N][MAX_N]){ ::n = n;
     rep(i,0,n+1) rep(j,0,n+1) rep(t,0,2) SID[i][j][t] = state(i, j, t).id, SIDd[i][j] = SID[i][j][0]>>1;
     rep(i,0,maxn*maxn*2) SS[i] = state(i);
     rep(i,0,n) rep(j,0,n) {
          if(A[i][j]){
               B[i][j] = true;
               rep(a,0,n) {
                    out[SIDd[a][i]]++;
               }
          }
     }
     rep(i,0,n) {
          rep(j,0,n) out[SIDd[i][n]]++;
     }
     calc();
     if(!win[SID[n][n][0]]) return -1;
     u = nxt[SIDd[n][n]], v = n;
     return u;
}

// don't modify the main function
// int main() {
//     cin.tie(0) -> sync_with_stdio(0);
//     int N;
//     cin >> N;
//     bool A[MAX_N][MAX_N];
//     for (int i = 0; i < N; i++) {
//         for (int j = 0; j < N; j++) {
//             cin >> A[i][j];
//         }
//     }
//     int P = start(N,A);
//     cout << P << endl;
//     int R;
//     cin >> R;
//     while (true) {
//         if (P == R) break;
//         P = nextMove(R);
//         cout << P << endl;
//         if (P == R) break;
//         cin >> R;
//     }
// }
      

// int main(){
//      cin.tie(0) -> sync_with_stdio(0);
//      cin >> n;
//      rep(i,0,n) rep(j,0,n) {
//           bool k; cin >> k;
//           if(k){
//                rep(a,0,n) {
//                     add_edge(state(a, i, 1), state(a, j, 0));
//                     add_edge(state(i, a, 0), state(j, a, 1));
//                }
//           }
//      }
//      rep(i,0,n) rep(j,0,n) add_edge(state(i, j, 0), state(i, j, 1));
//      rep(i,0,n) {
//           add_edge(state(n, n, 0), state(i, n, 1)); 
//           rep(j,0,n) add_edge(state(i, n, 1), state(i, j, 0));
//      }
//      calc();
//      rep(i,0,n) rep(j,0,n) {
//           int ID = state(i, j, 0).id;
//           if(!win[ID]) cout << -1 << ' ';
//           else cout << i << ',' << j << ',' << nxt[ID] << ' ';
//           if(j == n-1) cout << '\n';
//      }
//      if(!win[state(n, n, 0).id]) return -1;
//      cr = state(nxt[state(n, n, 0).id], n, 1);


//      cout << '#' << cr.u << endl;
//      while(cr.u - cr.v || cr.u == n){
//           int a; cin >> a;
//           cout << '#' << nextMove(a) << endl;
//      }
//      return 0;
// }

/*
4
0 1 0 1
1 0 1 0 
0 1 0 1
1 0 1 0

3
0 1 1
1 0 1 
1 1 0

*/

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