Submission #550719

#TimeUsernameProblemLanguageResultExecution timeMemory
550719Zhora_004Graph (BOI20_graph)C++17
5 / 100
1088 ms320 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <string> #include <sstream> #include <iomanip> #include <map> #include <unordered_map> #include <stack> #include <cstdio> #include <climits> #include <tuple> #include <ctime> #include <cstring> #include <numeric> #include <functional> #include <chrono> #include <cassert> #include <bitset> #include <fstream> //#include <bit> //#include <ranges> //#include <numbers> #define itn int #define sacnf scanf #define sz(a) ((int)((a).size())) // printf("%.10f\n", ans); /*ofstream fout("timeline.out"); ifstream fin("timeline.in");*/ using ll = long long; using namespace std; const ll mod = 1e9 + 7; const int N = 2e5 + 1, inf = 1e9; int n, m; double ans = 1000; vector<double> v, res; vector<vector<int>> e; double calc() { for (int i = 0; i < m; i++) { int a = e[i][0], b = e[i][1], c = e[i][2]; a--, b--; if (v[a] + v[b] != c) return 1000; } double sum = 0; for (int i = 0; i < n; i++) sum += abs(v[i]); return sum; } void solve() { if (sz(v) == n) { double sum = calc(); if (sum < ans) { ans = sum; res = v; } return; } for (double i = -5; i <= 5; i += 0.5) { v.push_back(i); solve(); v.pop_back(); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; e = vector<vector<int>>(m, vector<int>(3)); for (int i = 0; i < m; i++) for (int j = 0; j < 3; j++) cin >> e[i][j]; solve(); if (ans != 1000) { cout << "YES\n"; for (double& i : res) cout << i << " "; } else cout << "NO\n"; 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...