Submission #1182277

#TimeUsernameProblemLanguageResultExecution timeMemory
1182277qwushaGraph (BOI20_graph)C++20
58 / 100
273 ms14924 KiB
#include <bits/stdc++.h> using namespace std; /* #pragma GCC optimize("O3") #include <bitset> #pragma GCC target("avx2")*/ #define fi first #define se second #define int long long typedef long long ll; typedef long double ld; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); int inf = 1e15; vector<vector<pair<int, int>>> g; vector<int> val; int curbest = inf; int nowsum = 0; bool dfs(int v, int q) { val[v] = q; nowsum += abs(q); if (nowsum >= curbest) return 0; for (auto [u, w] : g[v]) { if (val[u] != inf) { if (val[u] + val[v] != w) return 0; } else { int res = dfs(u, w - val[v]); if (res == 0) return 0; } } return 1; } vector<int> col; void dfs_comp(int v, int c) { col[v] = c; for (auto [u, w] : g[v]) { if (col[u] == -1) { dfs_comp(u, c); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; g.resize(n); for (int i = 0; i < m; i++) { int v, u, w; cin >> v >> u >> w; g[v - 1].push_back({u - 1, w * 2}); g[u - 1].push_back({v - 1, w * 2}); } col.resize(n, -1); vector<int> boss; for (int i = 0; i < n; i++) { if (col[i] == -1) { boss.push_back(i); dfs_comp(i, boss.size() - 1); } } vector<vector<int>> comps(boss.size()); for (int i = 0; i < n; i++) { comps[col[i]].push_back(i); } val.assign(n, inf); bool done = 1; int answer = 0; vector<pair<int, int>> bq(boss.size()); for (int co = 0; co < boss.size(); co++) { bool ok = 0; int indb = -1; curbest = inf; int bst = -1; for (int qw = 0; qw <= 35 ; qw++) { int st = comps[co][rnd() % comps[co].size()]; for (int q = 0; q < 6; q++) { nowsum = 0; for (auto el : comps[co]) { val[el] = inf; } if (dfs(st, q)) { ok = 1; if (nowsum < curbest) { curbest = nowsum; indb = q; bst = st; } } } } bq[co] = {indb, bst}; if (ok == 0) { done = 0; break; } answer += curbest; } if (done == 0) { cout << "NO" << '\n'; return 0; } else { cout << "YES" << '\n'; for (int i = 0; i < n; i++) { val[i] = inf; } curbest = inf; nowsum = 0; for (int co = 0; co < boss.size(); co++) { dfs(bq[co].se, bq[co].fi); } for (auto el : val) { cout << el * 0.5 << ' '; } cout << '\n'; } }
#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...