Submission #1053306

#TimeUsernameProblemLanguageResultExecution timeMemory
1053306Zbyszek99Cop and Robber (BOI14_coprobber)C++17
0 / 100
42 ms17072 KiB
#include <bits/stdc++.h> #include "coprobber.h" #define rep(i,a,b) for(int i = a; i <= b; i++) #define pii pair<int,int> #define pb push_back using namespace std; struct dp { int rob,police,move; }; // DP[police][robber][turn] bool DP[MAX_N][MAX_N][2]; int zlicz[MAX_N][MAX_N][2]; int where_go[MAX_N][MAX_N]; vector<dp> graf2[MAX_N][MAX_N][2]; vector<int> graf[MAX_N]; int n; int cur_poz; int start(int N, bool A[MAX_N][MAX_N]) { n = N; queue<dp> winning_pos; rep(i,0,n-1) { rep(j,0,n-1) { if(A[i][j] == 1) { graf[i].push_back(j); } } } rep(i,0,n-1) { rep(j,0,n-1) { for(auto& it: graf[j]) { zlicz[i][j][1]++; } zlicz[i][j][0] = 0; } } rep(i,0,n-1) { winning_pos.push({i,i,0}); winning_pos.push({i,i,1}); zlicz[i][i][0] = 1; zlicz[i][i][1] = 0; } while(!winning_pos.empty()) { dp t = winning_pos.front(); winning_pos.pop(); // cout << t.police << " " << t.rob << " " << t.move << " win\n"; DP[t.police][t.rob][t.move] = 1; if(t.move == 0) { for(auto it: graf[t.police]) { zlicz[it][t.rob][1]--; //cout << it << " " << t.rob << " " << 1 << " " << zlicz[it][t.rob][1] << " new\n"; if(zlicz[it][t.rob][1] == 0) { where_go[it][t.rob] = t.police; winning_pos.push({t.rob,it,1}); } } zlicz[t.police][t.rob][1]--; // cout << t.police << " " << t.rob << " " << 1 << " " << zlicz[t.police][t.rob][1] << " new\n"; if(zlicz[t.police][t.rob][1] == 0) { where_go[t.police][t.rob] = t.police; winning_pos.push({t.rob,t.police,1}); } } if(t.move == 1) { for(auto it: graf[t.rob]) { zlicz[t.police][it][0]++; // cout << t.police << " " << it << " " << 0 << " " << zlicz[t.police][it][0] << " new\n"; if(zlicz[t.police][it][0] == 1) { winning_pos.push({it,t.police,0}); // where_go[t.police][it] = } } } } rep(start,0,n-1) { bool is = true; rep(end,0,n-1) { if(DP[start][end][0] == false) { // cout << start << " " << end << " se\n"; is = false; break; } } if(is) { cur_poz = start; return start; } } return -1; } int nextMove(int R) { cur_poz = where_go[cur_poz][R]; return cur_poz; } // int main() // { // int n; // cin >> n; // bool A[500][500]; // rep(i,0,n-1) // { // rep(j,0,n-1) // { // cin >> A[i][j]; // } // } // int poz = start(n,A); // cout << "police: " << poz << "\n"; // if(poz == -1) // { // return 0; // } // cout << "Rob poz: "; // int rob; // cin >> rob; // while(poz != rob) // { // poz = nextMove(rob); // cout << "new poz: " << poz << "\n"; // cout << "Rob: "; // cin >> rob; // } // }

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:41:23: warning: unused variable 'it' [-Wunused-variable]
   41 |             for(auto& it: graf[j])
      |                       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...