제출 #584509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584509		MohammadAghil	경찰관과 강도 (BOI14_coprobber)	C++17	0 / 100	31 ms	48376 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*2];
vector<int> adjr[maxn*maxn*2], adj[maxn*maxn*2];
bool win[maxn*maxn*2], B[maxn][maxn];
int nxt[maxn*maxn*2];

void calc(){
     // rep(i,0,n) rep(j,0,n){
     //      cout << i << ' ' << j << ": \n";
     //      for(int c: adj[state(i, j, 0).id]){
     //           cout << state(c).u << ' ' << state(c).v << '\n';
     //      }
     // }
     vector<int> winners;
     rep(i,0,n) rep(t,0,2) winners.pb(state(i, i, t).id);
     while(sz(winners)){
          int r = winners.back(); winners.pop_back();
          win[r] = true;
          state R(r);
          for(int c: adjr[r]){
               if(win[c]) continue;
               cnt[c]++;
               state S(c);
               if(S.nb){
                    if(cnt[c] == sz(adj[c])) winners.pb(c);
               }else winners.pb(c), nxt[c] = R.u;
          }
     }
}

void add_edge(state a, state b){
     adj[a.id].pb(b.id);
     adjr[b.id].pb(a.id);
}

state cr;

int nextMove(int r){
     cr = state(cr.u, r, 0);
     assert(B[cr.u][nxt[cr.id]] || nxt[cr.id] == n || cr.u == n);
     cr = state(nxt[cr.id], r, 1);
     assert(cr.u < n);
     return cr.u;
}

int start(int n, bool A[MAX_N][MAX_N]){ ::n = n;
     rep(i,0,n) rep(j,0,n) {
          if(A[i][j]){
               B[i][j] = true;
               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) {
          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();
     if(!win[state(n, n, 0).id]) return -1;
     cr = state(n, n, 0);
     return nxt[cr.id];
}

// 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) {
//           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();
//      if(!win[state(n, n, 0).id]) return cout << -1 << '\n', 0;
//      cr = state(n, n, 0);
//      cout << '#' <<nxt[cr.id] << endl;
//      while(cr.u - cr.v || cr.u == n){
//           int a; cin >> a;
//           cout << '#' << nextMove(a) << endl;
//      }
//      return 0;
// }

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