제출 #1260504

#제출 시각아이디문제언어결과실행 시간메모리
1260504miniobGraph (BOI20_graph)C++20
100 / 100
136 ms12800 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> graph[100007]; bool odw[100007]; int tab1[100007]; int tab2[100007]; long double odp[100007]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; graph[a].push_back({b, c}); graph[b].push_back({a, c}); } for (int i = 1; i <= n; i++) { if (!odw[i]) { queue<int> q; odw[i] = 1; tab1[i] = 1; tab2[i] = 0; q.push(i); vector<int> spojn; spojn.push_back(i); bool czyzdef = false; int gdzie = 0; while (!q.empty()) { int cur = q.front(); q.pop(); for (auto x : graph[cur]) { if (!odw[x.first]) { odw[x.first] = 1; tab1[x.first] = -tab1[cur]; tab2[x.first] = x.second - tab2[cur]; q.push(x.first); spojn.push_back(x.first); } else { if (tab1[cur] + tab1[x.first] == 0) { if (tab2[cur] + tab2[x.first] != x.second) { cout << "NO" << endl; return 0; } } else { int gdzie2; if(tab1[cur] + tab1[x.first] == 2) { gdzie2 = x.second - tab2[cur] - tab2[x.first]; } else { gdzie2 = tab2[cur] + tab2[x.first] - x.second; } if (!czyzdef) { czyzdef = true; gdzie = gdzie2; } else if (gdzie != gdzie2) { cout << "NO" << endl; return 0; } } } } } long double x; if (czyzdef) { x = (long double)gdzie / 2.0; } else { vector<long double> domed; for (int y : spojn) { domed.push_back(-(long double)tab1[y] * (long double)tab2[y]); } sort(domed.begin(), domed.end()); if (domed.size() % 2 == 1) { x = domed[domed.size()/2]; } else { x = (domed[domed.size()/2 - 1] + domed[domed.size()/2]) / 2.0; } } for (int y : spojn) { odp[y] = (long double)tab1[y] * x + (long double)tab2[y]; } } } cout << "YES" << endl; for (int i = 1; i <= n; i++) { cout << fixed << setprecision(10) << odp[i] << " "; } cout << endl; 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...