제출 #81214

#제출 시각아이디문제언어결과실행 시간메모리
81214wzy경찰관과 강도 (BOI14_coprobber)C++11
100 / 100
945 ms12284 KiB
#include <bits/stdc++.h> #include "coprobber.h" using namespace std; bool G[505][505][2]; int R[505][505]; int AD[505]; int n; tuple<int,int,int> P[505][505][2]; // Game Theory // G[i][j][0] wins if there is a k such that G[k][j][1] is winning // G[i][j][1] wins if all k adjacence to j G[i][k][0] is true int currA = 0 , currB = -1; int start(int N, bool A[MAX_N][MAX_N]) { n = N; queue<tuple<int,int,int > > q; for(int i = 0 ; i < N ; i++){ G[i][i][0] = 1; G[i][i][1] = 1; q.push(make_tuple(i,i,0)); q.push(make_tuple(i,i,1)); } // fill R[][] for(int i = 0 ; i < n; i++){ for(int j = 0 ; j < n; j ++){ for(int k = 0 ; k < n; k ++){ if(k == j) continue; R[i][j] = R[i][j] + A[j][k]; } } } while(!q.empty()){ tuple<int,int,int> u = q.front(); q.pop(); if(get<2>(u)){ for(int i = 0 ; i < n; i++){ if(A[i][get<0>(u)] || i == get<0>(u)){ if(G[i][get<1>(u)][0] == 0){ G[i][get<1>(u)][0] = 1; tuple<int,int,int> t = u; get<0>(t) = i, get<2>(t) = 0; P[get<0>(t)][get<1>(t)][get<2>(t)] = u; q.push(t); } } } } else{ for(int i = 0 ; i < n; i ++){ if(A[i][get<1>(u)]){ R[get<0>(u)][i]--; if(R[get<0>(u)][i] == 0){ G[get<0>(u)][i][1] = true; tuple<int,int,int> t = u; get<1>(t) = i; get<2>(t) = 1; P[get<0>(t)][get<1>(t)][get<2>(t)] = u; //cout<< get<0>(u) <<" " << get<1>(u) <<" " << get<2>(u) << endl; //cout<< get<0>(t) <<" " << get<1>(t) <<" " << get<2>(t) << endl; q.push(t); } } } } } bool can = true; for(int i = 0 ; i < n; i ++){ if(!G[0][i][0]) can = false; } if(can){ return 0; } else{ return -1; } } int nextMove(int R) { currB = R; tuple<int,int,int> L = P[currA][currB][0]; return currA = get<0>(L); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...