Submission #1280721

#TimeUsernameProblemLanguageResultExecution timeMemory
1280721avighnaStray Cat (JOI20_stray)C++20
100 / 100
52 ms13940 KiB
#include <queue> #include <string> #include <vector> namespace { std::string s = "110100"; std::vector<int> graph(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) { std::vector<int> x(M, -1); std::vector<std::vector<int>> adj(N); for (int i = 0; i < M; ++i) { adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } std::vector<bool> vis(N); std::vector<int> dep(N); std::queue<int> q; q.push(0); vis[0] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int &i : adj[u]) { if (vis[i]) { continue; } vis[i] = true; dep[i] = dep[u] + 1; q.push(i); } } for (int i = 0; i < M; ++i) { x[i] = std::min(dep[U[i]], dep[V[i]]) % 3; } return x; } std::vector<int> tree(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) { std::vector<std::vector<std::pair<int, int>>> adj(N); for (int i = 0; i < M; ++i) { adj[U[i]].push_back({V[i], i}); adj[V[i]].push_back({U[i], i}); } std::vector<int> ans(M); auto dfs = [&](auto &&self, int u, int p, int c, int st) -> void { if (adj[u].size() != 2) { if (st != -1) { st = -1; } for (auto &[i, edge_idx] : adj[u]) { if (i == p) { continue; } ans[edge_idx] = c; self(self, i, u, !ans[edge_idx], st); } return; } if (st == -1) { st = s.find(!c + '0') + 1; } st = st % s.length(); for (auto &[i, edge_idx] : adj[u]) { if (i == p) { continue; } ans[edge_idx] = s[st] - '0'; self(self, i, u, !ans[edge_idx], st + 1); } }; dfs(dfs, 0, -1, 0, -1); return ans; } } // namespace std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) { if (A == 2) { return tree(N, M, A, B, U, V); } return graph(N, M, A, B, U, V); }
#include <algorithm> #include <string> #include <vector> namespace { int A, B; std::string corr = "110100"; std::vector<std::string> poss; int prev = -1; bool fixed = false; std::string picked; int graph(std::vector<int> y) { std::vector<int> vals; for (int i = 0; i < 3; ++i) { for (int j = 0; j < y[i]; ++j) { vals.push_back(i); } } int max = *std::max_element(vals.begin(), vals.end()); int min = *std::min_element(vals.begin(), vals.end()); if (max - min <= 1) { return min; } return max; } int tree(std::vector<int> y) { auto pick = [&](int x) { picked.push_back((prev = x == -1 ? prev : x) + '0'); return x == -1 ? x : prev; }; int z = y[0] + (prev == 0), o = y[1] + (prev == 1); if (y[0] == 0 and y[1] == 0) { fixed = true; return pick(-1); } auto minority = [&]() { if (o < z) { return (o - (prev == 1)) ? 1 : -1; } return (z - (prev == 0)) ? 0 : -1; }; if (z != o and o != 0 and z != 0) { fixed = true; return pick(minority()); } if (fixed) { return pick((o - (prev == 1)) > (z - (prev == 0)));; } if (prev == -1) { if (o == 0) { picked.push_back('0'); } else if (z == 0) { picked.push_back('1'); } else { picked.push_back((o <= z) + '0'); } } int will = pick((o - (prev == 1)) > (z - (prev == 0))); if (picked.length() == 5) { fixed = true; auto it = std::find(poss.begin(), poss.end(), picked); if (it != poss.end()) { return pick(-1); } } return will; } } // namespace void Init(int A, int B) { ::A = A; ::B = B; for (int i = 0; i < 6; ++i) { std::string t; for (int j = 0; j < 5; ++j) { t.push_back(corr[(i + j) % 6]); } poss.push_back(t); } } int Move(std::vector<int> y) { if (A == 2) { return tree(y); } return graph(y); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...