Submission #550855

#TimeUsernameProblemLanguageResultExecution timeMemory
550855Zhora_004Graph (BOI20_graph)C++17
5 / 100
1 ms212 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 limit = 6; const int N = 2e5 + 1, inf = 1e9; struct Edge { int v, w; }; int n, m; vector<bool> vis; vector<int> comp, ans; vector<vector<Edge>> gp; void dfs1(int u) { vis[u] = 1; comp.push_back(u); for (Edge& e : gp[u]) if (!vis[e.v]) dfs1(e.v); } void dfs2(int u, int val) { vis[u] = 1; ans[u] = val; for (Edge& e : gp[u]) if (!vis[e.v]) dfs2(e.v, e.w - val); } int ok() { int sum = 0; for (int& u : comp) { for (Edge& e : gp[u]) { int v = e.v, w = e.w; if (!(-limit <= ans[u] && ans[u] <= limit && -limit <= ans[v] && ans[v] <= limit && ans[u] + ans[v] == w)) return inf; } sum += abs(ans[u]); } return sum; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; vis = vector<bool>(n); ans = vector<int>(n); gp = vector<vector<Edge>>(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 (!vis[i]) { comp.clear(); dfs1(i); int mn = inf, num = inf; for (int val = -limit; val <= limit; val++) { for (int& u : comp) vis[u] = 0; dfs2(i, val); int sum = ok(); if (sum < mn) { mn = sum; num = val; } } if (num == inf) return cout << "NO", 0; for (int& u : comp) vis[u] = 0; dfs2(i, num); } } cout << "YES\n"; for (int& i : ans) { if (i == -1) cout << "-0.5"; else { cout << i / 2; if (abs(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...