Submission #1182364

#TimeUsernameProblemLanguageResultExecution timeMemory
1182364qwushaGraph (BOI20_graph)C++20
34 / 100
737 ms28016 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; vector<int> chan; bool dfs(int v, int q) { chan.push_back(v); 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); } } } int K = 100; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; g.resize(n); unordered_map<int, int> mp; for (int i = 0; i < m; i++) { int v, u, w; cin >> v >> u >> w; if (mp.find((v - 1) * 1e7 + (u - 1)) != mp.end()) { if (mp[(v - 1) * 1e7 + (u - 1)] != w * 2) { cout << "NO" << '\n'; return 0; } } else { mp[(v - 1) * 1e7 + (u - 1)] = w * 2; mp[(u - 1) * 1e7 + (v - 1)] = w * 2; } g[v - 1].push_back({u - 1, w * 2}); g[u - 1].push_back({v - 1, w * 2}); } vector<int> indbig(n, -1); map<int, int> indnorm; int B = 0; for (int i = 0; i < n; i++) { if (g[i].size() > K) { indbig[i] = B; indnorm[B] = i; B++; } } vector<vector<pair<int, int>>> gB(B); for (int i = 0; i < n; i++) { if (indbig[i] == -1) continue; for (auto [u, q] : g[i]) { if (indbig[u] != -1) { gB[indbig[i]].push_back({indbig[u], q}); } } } vector<pair<int, int>> know; for (int i = 0; i < n; i++) { if (indbig[i] == -1) { for (auto [j, w1] : g[i]) { for (auto [q, w2] : g[i]) { if (j == q) continue; if (mp.find(j * 1e7 + q) != mp.end()) { int w3 = mp[j * 1e7 + q]; if (w1 != w2 || w2 != w3 || w1 != w3) { if (w1 + w2 + w3 == 8) { if (w1 == 4) know.push_back({q, 0}); else if (w2 == 4) know.push_back({j, 0}); else know.push_back({i, 0}); } else { if (w1 == 2) know.push_back({q, 3}); else if (w2 == 2) know.push_back({j, 3}); else know.push_back({i, 3}); } } } } } } } if (1) { for (int i = 0; i < B; i++) { for (int j = i + 1; j < B; j++) { int ni = indnorm[i], nj = indnorm[j]; if (mp.find(ni * 1e7 + nj) == mp.end()) continue; for (int q = j + 1; q < B; q++) { int nq = indnorm[q]; if (mp.find(ni * 1e7 + nq) != mp.end() && mp.find(nq * 1e7 + nj) != mp.end()) { int w1 = mp[ni * 1e7 + nj]; int w2 = mp[ni * 1e7 + nq]; int w3 = mp[nj * 1e7 + nq]; if (w1 + w2 + w3 == 8) { if (w1 == 4) know.push_back({nq, 0}); else if (w2 == 4) know.push_back({nj, 0}); else know.push_back({ni, 0}); } else { if (w1 == 2) know.push_back({nq, 3}); else if (w2 == 2) know.push_back({nj, 3}); else know.push_back({ni, 3}); } } } } } } 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); } vector<pair<int, int>> known(boss.size(), {-1, -1}); for (auto par : know) { known[col[par.fi]] = par; } val.assign(n, inf); bool done = 1; int answer = 0; vector<pair<int, int>> bq(boss.size()); vector<int> num(boss.size()); for (int i = 0; i < boss.size(); i++) { double r = (double)comps[i].size() / (double)n; num[i] = max(1ll, (int)(r * 15)); } for (int co = 0; co < boss.size(); co++) { bool ok = 0; int indb = -1; curbest = inf; int bst = -1; if (known[co].fi != -1) { int st = known[co].fi; int stval = known[co].se; nowsum = 0; for (auto el : chan) { val[el] = inf; } chan.clear(); if (dfs(st, stval)) { ok = 1; if (nowsum < curbest) { curbest = nowsum; indb = stval; bst = st; } } } else { for (int qw = 0; qw < num[co]; qw++) { int st = comps[co][rnd() % comps[co].size()]; int l = -18, r = 25; for (int q = 0; q <= r; q++) { nowsum = 0; for (auto el : chan) { val[el] = inf; } chan.clear(); if (dfs(st, q)) { ok = 1; if (nowsum < curbest) { curbest = nowsum; indb = q; bst = st; } } } for (int q = -1; q >= l; q--) { nowsum = 0; for (auto el : chan) { val[el] = inf; } chan.clear(); 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...