Submission #554665

#TimeUsernameProblemLanguageResultExecution timeMemory
554665ollelCop and Robber (BOI14_coprobber)C++14
0 / 100
0 ms208 KiB
using namespace std; #include <bits/stdc++.h> #define rep(i,a,b) for(int i = a; i < b; i++) #define pb push_back typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<bool> vb; typedef long long ll; typedef pair<int,int> pii; #include "coprobber.h" int n; vvi adj; vector<set<int>> adj_set; vector<set<int>> in_cycle; int cop = 0; void cycle_dfs(int x, int camefrom, vi & depth, vi & parent, vi & backDepth) { // highest depth of back edge, lowest down, max length of cycle backDepth[x] = depth[x]; for (auto & j : adj[x]) { if (j == camefrom) continue; if (depth[j] == -1) { depth[j] = depth[x] + 1; parent[j] = x; cycle_dfs(j, x, depth, parent, backDepth); } else { backDepth[x] = min(backDepth[x], depth[j]); } } } int start(int N, bool A[MAX_N][MAX_N]) { n = N; adj.resize(n); rep(i,0,n) { rep(j,0,n) { if (A[i][j]) adj[i].pb(j); } } vi depth(n, -1); vi backDepth(n, -1), parent(n, -1); depth[0] = 0; cycle_dfs(0, -1, depth, parent, backDepth); in_cycle.resize(n); rep(i,0,n) { int node = i, cycle = 1, back = backDepth[i]; in_cycle[i].insert(i); while (depth[node] > back) { cycle++; back = min(back, backDepth[node]); node = parent[node]; in_cycle[i].insert(node); if (cycle > 4) return -1; } } rep(i,0,n) for (auto & j : in_cycle[i]) for (auto & k : in_cycle[i]) in_cycle[j].insert(k); // rep(i,0,n) { // for (auto j : in_cycle[i]) cout << j << " "; // cout << endl; // } adj_set.resize(n); rep(i,0,n) for (auto & j : adj[i]) adj_set[i].insert(j); return 0; } int nextMove(int robber) { return robber; if (adj_set[cop].find(robber) != adj_set[cop].end()) { return robber; } if (in_cycle[cop].find(robber) != in_cycle[cop].end()) { return cop; } vi back(n, -1); back[cop] = 0; queue<int> q; q.push(cop); while (!q.empty()) { int x = q.front(); q.pop(); for (auto j : adj[x]) { if (back[j] != -1) continue; back[j] = x; q.push(j); } } int y = robber; while (back[y] != cop) y = back[y]; return y; } // // int main() { // int n = 5; // vector<vector<bool>> a = {{0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {1, 0, 1, 0, 0}, {1, 0, 0, 0, 0}}; // start(n, a); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...