Submission #550726

#TimeUsernameProblemLanguageResultExecution timeMemory
550726Zhora_004Graph (BOI20_graph)C++17
0 / 100
1 ms340 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <string> #include <sstream> #include <iomanip> #include <map> #include <unordered_map> #include <stack> #include <cstdio> #include <climits> #include <tuple> #include <ctime> #include <cstring> #include <numeric> #include <functional> #include <chrono> #include <cassert> #include <bitset> #include <fstream> //#include <bit> //#include <ranges> //#include <numbers> #define itn int #define sacnf scanf #define sz(a) ((int)((a).size())) // printf("%.10f\n", ans); /*ofstream fout("timeline.out"); ifstream fin("timeline.in");*/ using ll = long long; using namespace std; const ll mod = 1e9 + 7; const int N = 2e5 + 1, inf = 1e9; int n, m, a, b; vector<bool> used; vector<int> ans, comp; vector<vector<pair<int, int>>> gp; void dfs1(int u) { used[u] = 1; comp.push_back(u); for (pair<int, int>& p : gp[u]) { if (p.second == 4) a = u, b = p.first; if (!used[p.first]) dfs1(p.first); } } void dfs2(int u, int val, int& sum) { // -4 <= val <= 4 // else optimize used[u] = 1; ans[u] = val; sum += abs(val); for (pair<int, int>& p : gp[u]) if (!used[p.first]) dfs2(p.first, p.second - val, sum); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; used = vector<bool>(n); ans = vector<int>(n, inf); gp = vector<vector<pair<int, int>>>(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; gp[--u].push_back({ --v, w * 2 }); gp[v].push_back({ u, w * 2 }); } for (int i = 0; i < n; i++) { if (!used[i]) { comp.clear(); a = b = -1; dfs1(i); int mn = inf, num = -1; int val = -100; for (; val <= 100; val++) { for (int& u : comp) used[u] = 0; int sum = 0; dfs2(a, val, sum); for (int& u : comp) { for (pair<int, int>& p : gp[u]) { int v = p.first; if (!(-4 <= ans[u] && ans[u] <= 4 && -4 <= ans[v] && ans[v] <= 4 && ans[u] + ans[v] == p.second)) { sum = inf; break; } } if (sum == inf) break; } if (sum < mn) mn = sum, num = val; } if (num != -1) { for (int& u : comp) used[u] = 0; int sum = 0; dfs2(a, num, sum); } else return cout << "NO", 0; } } cout << "YES\n"; for (int i = 0; i < n; i++) { if (ans[i] == -1) cout << "-0.5 "; else { cout << ans[i] / 2; if (abs(ans[i]) & 1) cout << ".5"; cout << " "; } } return 0; }
#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...