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 ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
#define double long double
p operator+(p &a, p &b)
{
return p(a.f + b.f, a.s + b.s);
}
p operator-(p &a, p &b)
{
return p(a.f - b.f, a.s - b.s);
}
bool equal(p &a, p &b)
{
return a.f * b.s == a.s * b.f;
}
p operator*(p &a, ll b)
{
return p(a.f * b, a.s * b);
}
void operator-=(p &a, p &b)
{
a.f -= b.f;
a.s -= b.s;
}
void operator+=(p &a, p &b)
{
a.f += b.f;
a.s += b.f;
}
p operator-(p &a)
{
return p(-a.f, -a.s);
}
const p zero = p(0, 0);
const p one = p(0, 1);
const p two = p(0, 2);
const p id = p(1, 0);
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vp constants{zero, one, two};
ll N, M;
cin >> N >> M;
vvp graph(N);
for (ll i = 0; i < M; i++)
{
ll a, b , c;
cin >> a >> b >> c; a--; b--;
graph[a].eb(b, c);
graph[b].eb(a, c);
}
vb visited(N, false);
vp function(N);
vector<double> put(N);
for (ll i = 0; i < N; i++)
{
if (visited[i]) continue;
vp curFunctions;
vp constraints;
stack<tri> dfs;
v comp;
dfs.emplace(i, id);
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (visited[top.f])
{
constraints.eb(top.s - function[top.f]);
continue;
}
visited[top.f] = true;
function[top.f] = top.s;
comp.pb(top.f);
curFunctions.pb(top.s);
for (auto x : graph[top.f]) dfs.emplace(x.f, constants[x.s] - top.s);
}
p solution(0, 0);
for (auto x : constraints)
{
if (x.f == 0 && x.s != 0)
{
cout << "NO\n";
return 0;
}
else if (x.f != 0)
{
if (!equal(solution,x))
{
cout << "NO\n";
return 0;
}
solution = x;
}
}
double assignment;
if (solution.f == 0)
{
p curFunction(0, 0);
vector<pair<double, p>> events;
double minEv = INF;
double minEvVal = -1;
for (p x : curFunctions)
{
if (x.f >= 0)
curFunction += x;
else
curFunction -= x;
if (x.f != 0)
{
events.eb(-x.s / x.f, x * (x.f >= 0? 1 : -1));
}
}
for (auto x : events)
{
if (curFunction.f * x.f + curFunction.s < minEv)
{
minEv = curFunction.f * x.f + curFunction.s;
minEvVal = x.f;
}
curFunction -= x.s;
curFunction -= x.s;
}
assignment = minEvVal;
}
else
{
assignment = (double)-solution.s / solution.f;
}
for (ll x : comp)
{
put[x] = assignment * function[x].f + function[x].s;
}
}
cout << "YES\n";
for (double x : put) cout << fixed << setprecision(10) << x << " ";
cout << "\n";
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... |