Submission #932163

#TimeUsernameProblemLanguageResultExecution timeMemory
932163Ghulam_JunaidGraph (BOI20_graph)C++17
0 / 100
2 ms4440 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]; double val[N], ans[N]; 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; for (auto [u, w] : g[v]){ if (vis[u]){ if (val[u] == w - val[v]) continue; val[u] = 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}); } poss.push_back(0); poss.push_back(0.5); poss.push_back(-0.5); for (int i = 1; i <= n; i ++){ if (vis[i]) continue; path.clear(); getpath(i); long double mn = 1e9; int sz = path.size(); for (int r = 0; r < 50; r ++){ for (double x : poss){ for (int v : path) vis[v] = 0; int ind = rng() % sz; int node = path[ind]; if (!r) node = i; val[node] = x; dfs(node); long double sm = 0; for (int v : path) sm += abs(val[v]); if (mn > sm){ mn = sm; for (int v : path) ans[v] = val[v]; } } } 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...