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;
#define int int64_t
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define unas mp(1e9, 1e9)
#define undef 1e15
bool contradiction = false;
struct Node {
int index;
set<pii> neigh;
pii exp = unas;
double minVal = undef;
};
bool operator==(const pii &x1, const pii &x2) {
return x1.f == x2.f && x1.s == x2.s;
}
bool operator!=(const pii &x1, const pii &x2) {
return x1.f != x2.f || x1.s != x2.s;
}
pii operator+(const pii &x1, const pii &x2) {
return mp(x1.f+x2.f, x1.s+x2.s);
}
int conv(const pii &x) {
if (x.f <= 0) return x.s;
else return -x.s;
}
void pPair(const pii &x) {
cout << x.f << " " << x.s << "\n";
}
void assignExp(vector<Node> &g, int idx) {
g[idx].exp = mp(1, 0);
// bfs
queue<int> q;
q.push(idx);
while (!q.empty()) {
int t=q.front();q.pop();
pii ex = g[t].exp;
for (pii x : g[t].neigh) {
if (g[x.f].exp != unas) continue;
g[x.f].exp = mp(-ex.f, x.s - ex.s);
q.push(x.f);
}
}
double search = 1e15;
q.push(idx);
vector<bool> v((int)g.size(), false);
v[idx]=true;
while (!q.empty()) {
int t=q.front();q.pop();
pii ex = g[t].exp;
for (pii x : g[t].neigh) {
if ((ex + g[x.f].exp).first != 0) {
// cout << t << " " << x.f << "\n";
// pPair(ex);pPair(g[x.f].exp);
pii res = ex + g[x.f].exp;
double lft = (double)x.s;
lft -= (double)res.s;
search = lft / (double)res.f;
while (!q.empty())q.pop();
break;
}
else if (!v[x.f]) {
v[x.f]=true;
q.push(x.f);
}
}
}
if (search == 1e15) {
q.push(idx);
vector<bool> visited((int)g.size(), false);
visited[idx]=true;
vector<int> coeff;
coeff.pb(conv(g[idx].exp));
while (!q.empty()) {
int t=q.front();q.pop();
for (pii x : g[t].neigh) {
if (!visited[x.f]) {
visited[x.f]=true;
coeff.pb(conv(g[x.f].exp));
q.push(x.f);
}
}
}
sort(coeff.begin(), coeff.end());
search = (double)coeff[(int)coeff.size()/2];
}
q.push(idx);
g[idx].minVal = search;
while (!q.empty()) {
int t=q.front();q.pop();
for (pii x : g[t].neigh) {
if (g[x.f].minVal == undef) {
g[x.f].minVal = (double)(g[x.f].exp.f) * search + (double)g[x.f].exp.s;
q.push(x.f);
}
}
}
q.push(idx);
vector<bool> visited((int)g.size(), false);
while (!q.empty()) {
int t=q.front();q.pop();
for (pii x : g[t].neigh) {
if (g[t].minVal + g[x.f].minVal != (double)x.s) contradiction = true;
// printf("case %ld %ld\n", t, x.f);
// printf("value of first : %lf, value of second : %lf, value of edge : %ld\n\n", g[t].minVal, g[x.f].minVal, x.s);
if (!visited[x.f]) {
visited[x.f]=true;
q.push(x.f);
}
}
}
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);
int n, m;cin>>n>>m;
vector<Node> g(n);
for (int i=0;i<n;i++) {
g[i].index = i;
}
for (int i=0;i<m;i++) {
int start, end, code;
cin >> start >> end >> code;
start--;end--;
if (g[start].neigh.find(mp(end, 3 - code)) != g[start].neigh.end()) {
cout << "NO\n";
return 0;
}
g[start].neigh.insert(mp(end, code));
g[end].neigh.insert(mp(start, code));
}
for (int i=0;i<n;i++) {
if (g[i].exp == unas) {
assignExp(g, i);
if (contradiction) {
cout << "NO\n";
return 0;
}
}
}
if (contradiction) {
cout << "NO\n";
return 0;
}
cout << "YES\n";
cout << g[0].minVal;
for (int i=1;i<n;i++) {
cout << " " << g[i].minVal;
}
cout << "\n";
}
# | 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... |