Submission #932279

#TimeUsernameProblemLanguageResultExecution timeMemory
932279Ghulam_JunaidGraph (BOI20_graph)C++17
34 / 100
23 ms5212 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e5 + 10; int n, m; bool vis[N]; vector<double> poss; vector<int> path; vector<pair<int, double>> g[N], loops; double val[N], ans[N]; long double sm; void getpath(int v){ vis[v] = 1; path.push_back(v); for (auto [u, w] : g[v]) if (!vis[u]) getpath(u); } void dfs(int v){ vis[v] = 1; sm += abs(val[v]); for (auto [u, w] : g[v]){ if (vis[u]){ if (val[u] == w - val[v]) continue; val[u] = 1e9; sm += 1e9; return; } val[u] = w - val[v]; dfs(u); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < m; i ++){ int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); if (u == v) loops.push_back({v, w}); } for (auto [v, w] : loops){ if (vis[v]) continue; path.clear(); getpath(v); for (int u : path) vis[u] = 0; val[v] = w / 2; dfs(v); for (int u : path){ ans[u] = val[u]; if (ans[u] >= 1e9){ cout << "NO" << endl; return 0; } } } poss.push_back(0); for (double i = 0; i < 9; i ++){ poss.push_back(i + 0.5); poss.push_back(i + 1); } for (int i = 1; i <= n; i ++){ if (vis[i]) continue; path.clear(); getpath(i); for (int v : path) vis[v] = 0; double mn = 1e9; int sz = path.size(); for (int r = 0; r < 4; r ++){ for (double x : poss){ int ind = rng() % sz; int node = path[ind]; if (!r) node = i; sm = 0; val[node] = x; dfs(node); if (mn > sm){ mn = sm; for (int v : path){ vis[v] = 0; ans[v] = val[v]; } } else{ for (int v : path) vis[v] = 0; } } } for (int v : path) vis[v] = 1; if (mn == 1e9){ cout << "NO" << endl; return 0; } } cout << "YES" << endl; for (int i = 1; i <= n; i ++) cout << ans[i] << " "; cout << endl; }
#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...