Submission #1186599

#TimeUsernameProblemLanguageResultExecution timeMemory
1186599versesrevGame (IOI14_game)C++20
42 / 100
1096 ms1280 KiB
#include <deque> #include <vector> #include <bitset> constexpr int N = 1500; int n{}; std::bitset<N> mask; std::vector<std::bitset<N>> edges; void initialize(int _n) { n = _n; edges.assign(n, {}); for (int i = 0; i < n; ++i) mask[i] = true; for (int i = 0; i < n; ++i) { edges[i] = ~edges[i] & mask; } } int hasEdge(int u, int v) { edges[u][v] = edges[v][u] = false; if (edges[v].count() > edges[u].count()) { std::swap(u, v); } std::bitset<N> not_visited = mask; std::bitset<N> new_vs; new_vs[u] = true, not_visited[u] = false; while (new_vs.any() and not_visited[v]) { std::bitset<N> next_new_vs; for (int i = 0; i < n; ++i) { if (new_vs[i]) { next_new_vs |= edges[i]; } } new_vs = next_new_vs & not_visited; not_visited &= ~new_vs; } if (not_visited[v]) { edges[u][v] = edges[v][u] = true; } return edges[u][v]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...