Submission #1256233

#TimeUsernameProblemLanguageResultExecution timeMemory
1256233jerzykGraph (BOI20_graph)C++20
0 / 100
2 ms2632 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100 * 1000 + 7; const int I = 1000 * 1000 * 1000; vector<pair<int, int>> ed[N]; pair<int, int> val[N]; vector<int> cur; long double answer[N]; void DFS(int v) { cur.push_back(v); for(int i = 0; i < (int)ed[v].size(); ++i) { if(val[ed[v][i].first].first != 0) continue; val[ed[v][i].first].first = -val[v].first; val[ed[v][i].first].second = ed[v][i].second - val[v].second; DFS(ed[v][i].first); } } bool Do() { bool czy = 1; vector<int> pos; long double x = -I - 10; for(int i = 0; i < (int)cur.size(); ++i) { int v = cur[i]; pos.push_back(val[v].first * val[v].second * -1); for(int j = 0; j < (int)ed[v].size(); ++j) { int ne = ed[v][j].first; if(val[v].first == val[ne].first) x = (long double)(ed[v][j].second - val[v].second - val[ne].second) / (long double)2; else if(val[v].second + val[ne].second != ed[v][j].second) czy = 0; } } sort(pos.begin(), pos.end()); if(x < -I) x = pos[(int)pos.size() / 2]; for(int i = 0; i < (int)cur.size(); ++i) { int v = cur[i]; answer[v] = x * (long double)val[v].first + (long double)val[v].second; } cur.clear(); return czy; } void Wynik(int &n) { bool czy = 1; for(int i = 1; i <= n; ++i) { if(val[i].first != 0) continue; val[i].first = 1; DFS(i); czy = (czy & Do()); } if(czy == 0) { cout << "NO\n"; return; } cout << "YES\n"; cout << fixed << setprecision(1); for(int i = 1; i <= n; ++i) cout << answer[i] << " "; cout << "\n"; } void WczytajLiczby(int &n) { int m, a, b, c; cin >> n >> m; for(int i = 1; i <= m; ++i) { cin >> a >> b >> c; ed[a].push_back(make_pair(b, c)); ed[b].push_back(make_pair(a, c)); } } void Gra() { int n; WczytajLiczby(n); Wynik(n); } int main () { ios_base::sync_with_stdio(false); cin.tie(nullptr); Gra(); return 0; }
#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...