This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair <int, int> pii;
const int INF = 1e9;
const int MAXN = 2e5 + 10;
bool d1[MAXN];
int d2[MAXN];
int cost[MAXN];
bool mark1[MAXN];
bool mark2[MAXN];
vector <pii> e[MAXN];
vector <int> vec;
void dfs1(int v, int val)
{
mark1[v] = true;
cost[v] = val;
for (auto [u, w] : e[v])
{
if (mark1[u])
{
if (cost[v] + cost[u] != 2 * w)
{
cout << "NO" << endl;
exit(0);
}
}
else
{
dfs1(u, 2 * w - val);
}
}
}
int dfs2(int v)
{
mark2[v] = true;
vec.push_back((d1[v] ? d2[v] : -d2[v]));
for (auto [u, w] : e[v])
{
if (!mark2[u])
{
d1[u] = !d1[v];
d2[u] = 2 * w - d2[v];
int x = dfs2(u);
if (x < INF)
return x;
}
else
{
if (d1[v] ^ d1[u])
{
if (2 * w - d2[v] != d2[u])
{
cout << "NO" << endl;
exit(0);
}
}
else
{
return (w - (d2[v] + d2[u]) / 2) * (d1[v] ? -1 : 1);
}
}
}
return INF;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int v, u, w;
cin >> v >> u >> w;
e[v].push_back({u, w});
e[u].push_back({v, w});
}
for (int i = 1; i <= n; i++)
{
if (mark1[i])
continue;
int x = dfs2(i);
if (x == INF)
{
sort(vec.begin(), vec.end());
x = vec[(vec.size() / 2)];
}
dfs1(i, x);
vec.clear();
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++)
cout << (float) (cost[i] / (float) 2) << " ";
cout << endl;
}
# | 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... |