|
|
back to boardWA 44, can't find a mistacke i'm stuck with this problem for about 2 hours and still wa44. Any advices? Here is my code: #include <iostream> #include <vector> #include <algorithm> #include <string> #include <queue> #include<set> #include <fstream> #include <iomanip> #include <list> #include <stack> #include <map> #include <math.h> #include <unordered_map> using namespace std; vector<vector<int>> edges; vector<bool> used; void dfs(int from) { if (!used[from]) { used[from] = true; for (auto a : edges[from]) dfs(a); } } vector<bool> colours; bool coloringDfs(int from, bool color) { if (used[from]) {
} else { used[from] = true; colours[from] = color; for (auto a : edges[from]) if (used[a]) { if (colours[a] == color) return false; } else if(!coloringDfs(a, !color)) return false; return true; } } vector<int> meanings; bool coloringDfs2(int from, bool color, int min) { if (used[from]) {
} else { used[from] = true; meanings[from] = color+1+min; for (auto a : edges[from]) if (!coloringDfs2(a, !color,min)) return false; return true; } } int bfs(int from, int n) { vector<bool> us = vector<bool>(n, false); int currentLevel = 1; vector<int> v1; v1.push_back(from); us[from] = true; vector<int> v2; while (v1.size()) { for(auto a:v1) for(auto b: edges[a]) if (!us[b]) { us[b] = true; v2.push_back(b); } currentLevel++; swap(v1, v2); v2.clear(); } return currentLevel-2; } int bfs2(int from, int n) { vector<bool> us = vector<bool>(n, false); int currentLevel = 1; vector<int> v1; v1.push_back(from); meanings[from] = 1; us[from] = true; vector<int> v2; while (v1.size()) { for (auto a : v1) for (auto b : edges[a]) if (!us[b]) { us[b] = true; meanings[b] = currentLevel + 1; v2.push_back(b); } currentLevel++; swap(v1, v2); v2.clear(); } return currentLevel-1; } int main() { int m; int n; cin >> m >> n; used = vector<bool>(n,false); edges = vector<vector<int>>(n, vector<int>()); for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; --x; --y; edges[x].push_back(y); edges[y].push_back(x); }
colours = vector<bool>(n); for (int i = 0; i < n; ++i) { used = vector<bool>(n, false); if (!coloringDfs(0, 0)) { cout << -1; return 0; } }
dfs(0); meanings = vector<int>(n); for(int i = 0 ; i < n; ++i) if (!used[i]) { cout << 49; used = vector<bool>(n, false); meanings = vector<int>(n, 0); bool ok = false; for(int i = 0 ; i < n; ++i) if (!used[i]) { coloringDfs2(i, ok, 48 * ok); ok = !ok; } cout << endl; for (auto a : meanings) cout << a << " "; return 0; } int currentMax = bfs(0, n); int currentIndex = 0; for (int i = 1; i < n; ++i) { int x = bfs(i, n); if (x > currentMax) { currentMax = x; currentIndex = i; } } bfs2(currentIndex, n); cout << currentMax << endl; for (auto a : meanings) cout << a<<" ";
} |
|
|