Submission #906399

#TimeUsernameProblemLanguageResultExecution timeMemory
906399MONGraph (BOI20_graph)C++14
58 / 100
730 ms24820 KiB
#include<iostream> #include<random> #include<ctime> #include<vector> #include<bitset> #include<iomanip> #include<algorithm> #pragma GCC optimize("Ofast","fast-math") using namespace std; using pii = pair<int,int>; using pid = pair<int,double>; const double bulan[] = {0,0.5,-0.5,-1,1,-1.5,1.5,-2,2,2.5,-2.5,3,-3,3.5,-3.5,4,-4,4.5,-4.5, 5,-5,5.5,-5.5,6,6.5,-6,-6.5,7,-7,7.5,-7.5}; constexpr double eps = 1e-6; constexpr int NMAX = 1e5 + 1; mt19937 rng(time(nullptr)); bitset<NMAX> viz,fix; double ans[NMAX]; vector<pii> vecini[NMAX]; void dfs(int a,vector<int> &u) { u.emplace_back(a); viz[a] = 1; for(auto &it : vecini[a]) if(!viz[it.first]) dfs(it.first,u); } void go(int a,double v,vector<pid> &res) { res.push_back({a,v}); viz[a] = 1; ans[a] = v; for(auto &it : vecini[a]) { if(!viz[it.first]) go(it.first,it.second - v,res); } } long double ab(vector<pid> &h) { long double res = 0; for(auto &it : h) res += abs(it.second); return res; } bool ok(vector<int> &h) { for(auto &f : h) { for(auto &s : vecini[f]) { if(abs(ans[f] + ans[s.first] - s.second) > eps) return 0; } } return 1; } void solve(vector<int> &comp) { for(auto &v : comp) { if(fix[v]) { vector<pid> h; go(v,ans[v],h); for(auto &it : h) ans[it.first] = it.second; return; } } long double mini = 1e18; vector<pid> res; uniform_int_distribution<int> d(0,comp.size()-1); for(int ty = 0; ty < 3; ty++) { int mumu = comp[d(rng)]; for(auto &val : bulan) { for(auto &it : comp) viz[it] = 0; vector<pid> h; go(mumu,val,h); double now = ab(h); if(now < mini && ok(comp)) { mini = now; res.swap(h); } } } for(auto &it : res) ans[it.first] = it.second; } int main() { int n,m,a,b,c; cin >> n >> m; for(int i = 1; i <= m ; i++) { cin >> a >> b >> c; vecini[a].push_back({b,c}); vecini[b].push_back({a,c}); if(a == b) { fix[a] = 1; ans[a] = (1.0 * c / 2); } } vector<vector<int>> comps; for(int i = 1; i <= n ; i++) { if(!viz[i]) { vector<int> comp; dfs(i,comp); comps.push_back(comp); } } viz.reset(); for(auto &it : comps) solve(it); bool okk = 1; for(auto &c : comps) okk &= ok(c); if(!okk) cout << "NO"; else { cout << "YES\n"; for(int i = 1; i <= n ; i++) cout << fixed << setprecision(2) << ans[i] << " "; } }
#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...