#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
using namespace std;
pair <double,double> v[DIM];
vector <pair<int,int> > L[DIM];
vector <int> s,d,w;
int mrk[DIM];
map <pair<int,int>,int> f;
struct muchie{
int x,y,cost;
} mch[DIM];
double x;
int cnt,nod_special,ok;
int n,m,i,j,xx,y,c;
void dfs (int nod){
if (ok)
return;
mrk[nod] = 1;
s.push_back(nod);
w.push_back(nod);
for (auto it : L[nod]){
int vecin = it.first, val = it.second;
if (v[vecin].first == INF){ /// nu am mai ajuns aici
v[vecin] = make_pair(-v[nod].first,-v[nod].second + val);
} else {
if (v[vecin].first == -v[nod].second && v[vecin].second != -v[nod].second + val){
/// nu am solutie
ok = 1;
return;
}
if (v[vecin].first != -v[nod].first){ /// inseamna ca aflu x ul
x = 1.0*(val - v[vecin].second - v[nod].second) / (v[nod].first + v[nod].second);
/// acum trb sa refac (a,b) ale nodurilor deja procesate
s.push_back(vecin);
while (!s.empty()){
int idx = s.back();
double val2 = v[idx].first * x + v[idx].second;
v[idx] = make_pair(0,val2);
s.pop_back();
}
}
}
if (!mrk[vecin])
dfs (vecin);
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
ok = 0;
for (i=1;i<=m;i++){
cin>>xx>>y>>c;
L[xx].push_back(make_pair(y,c));
L[y].push_back(make_pair(xx,c));
if (xx > y)
swap (xx,y);
if (!f[make_pair(xx,y)])
f[make_pair(xx,y)] = c;
else {
if (f[make_pair(xx,y)] != c)
ok = 1;
}
mch[i] = {xx,y,c};
}
if (ok){
cout<<"NO";
return 0;
}
for (i=1;i<=n;i++){
//sol[i] = INF;
v[i] = make_pair(INF,INF);
/// valoarea din fiecare nod o sa fie de forma a*x + b
if (f[make_pair(i,i)])
v[i] = make_pair(0,1.0 * f[make_pair(i,i)] / 2.0);
}
for (i=1;i<=n;i++){
if (mrk[i])
continue;
v[i] = make_pair(1,0);
x = INF, ok = 0;
w.clear();
dfs (i);
if (ok){
cout<<"NO";
return 0;
}
if (w.size() == 1){
v[i].first = 0;
continue;
}
if (x == INF){
/// inseamna ca am mai multe solutii
d.clear();
for (auto it : w){
if (v[it].first < 0)
d.push_back(v[it].second);
else d.push_back(-v[it].second);
}
sort (d.begin(),d.end());
x = d[(d.size()-1)/2];
for (auto it : w){
double val = v[it].first * x + v[it].second;
v[it] = make_pair(0,val);
}
}
}
/// mai verific odata conditiile
ok = 0;
for (i=1;i<=m;i++){
int x = mch[i].x, y = mch[i].y;
if (v[x].second + v[y].second != mch[i].cost){
ok = 1;
break;
}}
if (ok)
cout<<"NO";
else{
cout<<"YES\n";
for (i=1;i<=n;i++)
cout<<v[i].second<<" ";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
answer = YES |
2 |
Correct |
4 ms |
4940 KB |
answer = YES |
3 |
Correct |
4 ms |
4940 KB |
answer = YES |
4 |
Correct |
3 ms |
4940 KB |
answer = NO |
5 |
Correct |
4 ms |
4940 KB |
answer = YES |
6 |
Correct |
3 ms |
5012 KB |
answer = YES |
7 |
Incorrect |
4 ms |
5068 KB |
jury has the better answer: jans = YES, pans = NO |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
answer = YES |
2 |
Correct |
4 ms |
4940 KB |
answer = YES |
3 |
Correct |
4 ms |
4940 KB |
answer = YES |
4 |
Correct |
3 ms |
4940 KB |
answer = NO |
5 |
Correct |
4 ms |
4940 KB |
answer = YES |
6 |
Correct |
3 ms |
5012 KB |
answer = YES |
7 |
Incorrect |
4 ms |
5068 KB |
jury has the better answer: jans = YES, pans = NO |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
answer = YES |
2 |
Correct |
4 ms |
4940 KB |
answer = YES |
3 |
Correct |
4 ms |
4940 KB |
answer = YES |
4 |
Correct |
3 ms |
4940 KB |
answer = NO |
5 |
Correct |
4 ms |
4940 KB |
answer = YES |
6 |
Correct |
3 ms |
5012 KB |
answer = YES |
7 |
Incorrect |
4 ms |
5068 KB |
jury has the better answer: jans = YES, pans = NO |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
answer = YES |
2 |
Correct |
4 ms |
4940 KB |
answer = YES |
3 |
Correct |
4 ms |
4940 KB |
answer = YES |
4 |
Correct |
3 ms |
4940 KB |
answer = NO |
5 |
Correct |
4 ms |
4940 KB |
answer = YES |
6 |
Correct |
3 ms |
5012 KB |
answer = YES |
7 |
Incorrect |
4 ms |
5068 KB |
jury has the better answer: jans = YES, pans = NO |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
answer = YES |
2 |
Correct |
4 ms |
4940 KB |
answer = YES |
3 |
Correct |
4 ms |
4940 KB |
answer = YES |
4 |
Correct |
3 ms |
4940 KB |
answer = NO |
5 |
Correct |
4 ms |
4940 KB |
answer = YES |
6 |
Correct |
3 ms |
5012 KB |
answer = YES |
7 |
Incorrect |
4 ms |
5068 KB |
jury has the better answer: jans = YES, pans = NO |
8 |
Halted |
0 ms |
0 KB |
- |