제출 #861198

#제출 시각아이디문제언어결과실행 시간메모리
861198Ellinor경찰관과 강도 (BOI14_coprobber)C++14
0 / 100
1390 ms17320 KiB
#include "coprobber.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens #pragma GCC optimize ("unroll-loops") #pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation #pragma GCC target("movbe") // byte swap #pragma GCC target("aes,pclmul,rdrnd") // encryption #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") typedef long long ll; #define rep(i, a, b) for (int i = (a); i < int(b); i++) typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define pb push_back // inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } ll INF = 1e15; ll mod = 1e9 + 7; // #define int ll #define float double int n; vector<vector<int>> adj; int cat = -1; vector<vector<vector<pii>>> dp; queue<array<int, 3>> q; void sol(int C, int R, int T) { // if (dp[C][R][T].first != -1) return dp[C][R][T].first; // :( if (C == R) { dp[C][R][T].first = 1; } if (T == 1) { for (int i : adj[R]) { if (dp[C][i][0].first == -1) q.push({C, i, 0}); } if (dp[C][R][0].first == -1) q.push({C, R, 0}); } else if (T == 0) { if (C != R) { for (int i : adj[R]) { if (dp[C][i][1].first != 1) { dp[C][R][0].first = 0; return; } } } dp[C][R][0].first = 1; for (int i : adj[C]) { if (dp[i][R][1].first == -1) { dp[i][R][1].first = 1; dp[i][R][1].second = C; q.push({i, R, 1}); } } } } int start(int N, bool A[MAX_N][MAX_N]) { n = N; adj.assign(n, {}); rep(i,0,n) { rep(j,i + 1,n) { if (A[i][j]) { adj[i].pb(j); adj[j].pb(i); } } } // dp.assign(n, vector<vector<pii>>(n, vector<pii>(2, {-1, -1}))); rep(i,0,n) { q.push({i, i, 0}); q.push({i, i, 1}); } while (!q.empty()) { auto x = q.front(); q.pop(); sol(x[0], x[1], x[2]); } rep(i,0,n) { rep(j,0,n) { rep(k,0,2) { cerr << dp[i][j][k].first << " "; } cerr << endl; } cerr << endl; } rep(i,0,n) { bool w = true; rep(j,0,n) { if (dp[i][j][1].first != 1) w = false; } if (w) { return cat = i; } } return -1; } int nextMove(int R) { if (cat == R) return cat; // return cat = dp[cat][R][1].second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...