Submission #566312

#TimeUsernameProblemLanguageResultExecution timeMemory
566312hoanghq2004Alternating Current (BOI18_alternating)C++14
0 / 100
3116 ms808736 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 1e5 + 10; int n, m, k; vector <int> s[N], g[N]; int color[N]; int dfs(int u, int c) { if (color[u] != -1) return (color[u] == c); color[u] = c; for (auto v: g[u]) { if (!dfs(v, c ^ 1)) return 0; } return 1; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { int L, R; cin >> L >> R; if (L <= R) { for (int j = L; j <= R; ++j) s[j].push_back(i); } else { for (int j = L; j <= n; ++j) s[j].push_back(i); for (int j = 1; j <= R; ++j) s[j].push_back(i); } } for (int i = 1; i <= n; ++i) { if (s[i].size() < 2) { cout << "impossible\n"; exit(0); } if (s[i].size() == 2) { g[s[i][0]].push_back(s[i][1]); g[s[i][1]].push_back(s[i][0]); } } memset(color, -1, sizeof(color)); for (int i = 1; i <= n; ++i) { int ok0 = 0, ok1 = 0; for (auto j: s[i]) { if (color[j] == 0) ok0 = 1; if (color[j] == 1) ok1 = 1; } if (ok0 && ok1) continue; random_shuffle(s[i].begin(), s[i].end()); if (!ok0) { for (auto j: s[i]) { if (color[j] == -1) { if (!dfs(j, 0)) { cout << "impossible\n"; exit(0); } ok0 = 1; } } if (!ok0) { cout << "impossible\n"; exit(0); } } for (auto j: s[i]) if (color[j] == 1) ok1 = 1; if (ok1) continue; random_shuffle(s[i].begin(), s[i].end()); for (auto j: s[i]) { if (color[j] == -1) { if (!dfs(j, 1)) { cout << "impossible\n"; exit(0); } ok1 = 1; } } if (!ok1) { cout << "impossible\n"; exit(0); } } for (int i = 1; i <= m; ++i) cout << color[i]; }
#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...