This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, a, b;
vector<bool> used;
vector<int> ans, comp;
vector<vector<pair<int, int>>> gp;
void dfs1(int u)
{
used[u] = 1;
comp.push_back(u);
for (pair<int, int>& p : gp[u])
{
if (p.second == 4) a = u, b = p.first;
if (!used[p.first]) dfs1(p.first);
}
}
void dfs2(int u, int val, int& sum)
{
// -4 <= val <= 4
// else optimize
used[u] = 1;
ans[u] = val;
sum += abs(val);
for (pair<int, int>& p : gp[u]) if (!used[p.first]) dfs2(p.first, p.second - val, sum);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
used = vector<bool>(n);
ans = vector<int>(n, inf);
gp = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
gp[--u].push_back({ --v, w * 2 });
gp[v].push_back({ u, w * 2 });
}
for (int i = 0; i < n; i++)
{
if (!used[i])
{
comp.clear();
a = b = -1;
dfs1(i);
int mn = inf, num = -1;
int val = -100;
if (a == -1) a = i;
for (; val <= 100; val++)
{
for (int& u : comp) used[u] = 0;
int sum = 0;
dfs2(a, val, sum);
for (int& u : comp)
{
for (pair<int, int>& p : gp[u])
{
int v = p.first;
if (!(-4 <= ans[u] && ans[u] <= 4 && -4 <= ans[v] && ans[v] <= 4 && ans[u] + ans[v] == p.second))
{
sum = inf;
break;
}
}
if (sum == inf) break;
}
if (sum < mn) mn = sum, num = val;
}
if (num != -1)
{
for (int& u : comp) used[u] = 0;
int sum = 0;
dfs2(a, num, sum);
}
else return cout << "NO", 0;
}
}
cout << "YES\n";
for (int i = 0; i < n; i++)
{
if (ans[i] == -1) cout << "-0.5 ";
else
{
cout << ans[i] / 2;
if (abs(ans[i]) & 1) cout << ".5";
cout << " ";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |