#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Linear {
double m,b;
bool operator==(Linear a) const {
return m==a.m && b==a.b;
}
};
Linear Inv(Linear a) {
return {a.m,-a.b*a.m};
}
Linear Compose(Linear a, Linear b) {
return {a.m*b.m,b.b*a.m+a.b};
}
Linear Intersect(Linear a,Linear b) {
return {0,-(a.b-b.b)/(a.m-b.m)};
}
Linear t1 = {-1,1};
Linear t2={-1,2};
Linear id={1,0};
vector<int> dsu;
vector<Linear> toParent;
vector<int> s;
void e() {
cout<<"NO";
exit(0);
}
pair<int,Linear> find(int a) {
if(dsu[a]==a) return {a,id};
auto [b,l] = find(dsu[a]);
return {b,Compose(l,toParent[a])};
}
void un(int a,int b,Linear type) {
auto [ap,la] = find(a);
auto [bp,lb] = find(b);
if(ap==bp) {
if(Compose(type,Compose(la,toParent[ap]))==Compose(lb,toParent[bp])) {
return;
}else {
if(!(toParent[ap]==id)) e();
if(la.m!=lb.m) e();
toParent[ap] = Intersect(Compose(type,la),lb);
}
}else {
if(s[bp]<s[ap]) {
swap(ap,bp);
swap(la,lb);
}
if(toParent[ap]==id) {
toParent[ap]=Compose(Inv(la),Compose(type,lb));
}else {
Linear atob = Compose(Inv(la),Compose(type,lb));
if(toParent[b]==id) {
toParent[b]=Compose(atob,toParent[a]);
toParent[a]=atob;
}else {
if(Compose(atob,toParent[a])==toParent[b]) {
toParent[a]=atob;
}else {
e();
}
}
}
dsu[ap]=bp;
s[bp]+=s[ap];
}
}
void Solve(vector<pair<int,Linear>> &g,vector<double> &res) {
sort(g.begin(), g.end(),[](pair<int,Linear> a,pair<int,Linear> b) {
return b.second.b>a.second.b;
});
double t = g[g.size()/2].second.b;
for(auto [a,l]:g) {
res[a] = Compose(l,{0,t}).b;
}
}
int main() {
int n,m;cin>>n>>m;
for (int i = 0; i < n; ++i) {
dsu.push_back(i);
toParent.push_back(id);
s.push_back(1);
}
for (int i = 0; i < m; ++i) {
int x,y,t; cin>>x>>y>>t; x--; y--;
if(t==1) {
un(x,y,t1);
}else {
un(x,y,t2);
}
}
vector<vector<pair<int,Linear>>> g(n);
vector<bool> type(n,true);
for (int i = 0; i < n; ++i) {
auto [a,l]=find(i);
l= Compose(l,toParent[a]);
if(l.m==0) type[a]=false;
g[a].push_back({i,l});
}
vector<double> res(n);
for (int i = 0; i < n; ++i) {
if(g[i].size()==0) continue;
if(type[i]) {
Solve(g[i],res);
}else {
for(auto u : g[i]) {
res[u.first]=u.second.b;
}
}
}
cout<<"Yes"<<endl;
for (int i = 0; i < n; ++i) {
cout<<res[i]<<" ";
}
}
Compilation message
Graph.cpp: In function 'std::pair<int, Linear> find(int)':
Graph.cpp:33:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | auto [b,l] = find(dsu[a]);
| ^
Graph.cpp: In function 'void un(int, int, Linear)':
Graph.cpp:37:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | auto [ap,la] = find(a);
| ^
Graph.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | auto [bp,lb] = find(b);
| ^
Graph.cpp: In function 'void Solve(std::vector<std::pair<int, Linear> >&, std::vector<double>&)':
Graph.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | for(auto [a,l]:g) {
| ^
Graph.cpp: In function 'int main()':
Graph.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | auto [a,l]=find(i);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Expected YES or NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Expected YES or NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Expected YES or NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Expected YES or NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Expected YES or NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
