#include <bits/stdc++.h>
using namespace std;
struct Node
{
vector<pair<Node*,bool>> neigh;
int x_parity = 0; // actual value = value + x*x_parity
float value = NAN;
bool seen = false; // collect_all_vi
bool seen2 = false; // set_x
variant<float,bool> assign(float val=0,int par=1) // float - unique solution for x
{ // bool - works for any/no x
if(!isnan(value))
{
if(x_parity==par) return val == value;
// solve linear equation x * x_parity + value == x*par + val
// x * (x_parity - par) == val - value
// x = val - value / (x_parity - par)
float x = ((float) val - value) / ((float) x_parity - par);
return x;
}
value = val;
x_parity = par;
float x = NAN;
for(auto[n,t] : neigh)
{
auto a = n->assign((1+t)-val,-par);
if(a.index()==0)
{
// unique solution for x found
if (!isnan(x) && x != get<float>(a)) return false;
x = get<float>(a);
}
else if (!get<bool>(a)) return false;
}
if(isnan(x)) return true;
return x;
}
void collect_v_i(vector<int>& v_i) // v_i in abs(x-v_i)
{
if(seen) return;
seen = true;
v_i.push_back(-value*x_parity);
for(auto[n,t] : neigh) n->collect_v_i(v_i);
}
void set_x(float x)
{
if(seen2) return;
seen2 = true;
value += x*x_parity;
for(auto[n,_] : neigh) n->set_x(x);
}
// need to decide for value of x (probably small, but uncertain)
// the total weigth is a sum of elements of type abs(v_i+x)
// collect all v_i (traversing) - x must be some -v_i. nlogn given sorting.
// binary search over larger/smaller than these and these elements, gives linear relationship
};
signed main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int N,M;
cin >> N >> M;
vector<Node> nodes(N);
for(int i = 0; i < M; i++)
{
int a,b,c;
cin >> a >> b >> c;
nodes[a-1].neigh.push_back({&nodes[b-1],c>1});
nodes[b-1].neigh.push_back({&nodes[a-1],c>1});
}
for(int t = 0; t < N; t++)
{
if(!isnan(nodes[t].value)) continue; // node already seen
auto a = nodes[t].assign();
if(a.index()==0) // a is a float => x is fixed
{
float x = get<float>(a);
nodes[t].set_x(x); // recursive
}
else
{
// a is a bool.
if (!get<bool>(a))
{
cout << "NO\n";
exit(0);
} // not possible.
// need to figure out optimal value for x.
vector<int> vi;
nodes[t].collect_v_i(vi);
sort(vi.begin(),vi.end());
int x = vi[0];
int cost = 0;
for(auto i : vi) cost += (i-x);
int min_cost = cost;
int min_x = x;
for(int i = 1; i < vi.size(); i++)
{
int next_x = vi[i];
cost -= (next_x-x)*(vi.size()-i);
cost += (next_x-x)*(i);
if (min_cost > cost)
{
int min_cost = cost;
int min_x = x;
}
}
nodes[t].set_x(min_x);
}
}
cout << "YES\n" << nodes[0].value;
for(int i = 1; i < N; i++) cout << " " << nodes[i].value;
cout << "\n";
// assign "x" to some node
// continue traversing, getting either x+int or int-x for some edges
// if reencounter, might constrain x, set.
// repeat for all connected components
}
Compilation message
Graph.cpp:11:5: error: 'variant' does not name a type
11 | variant<float,bool> assign(float val=0,int par=1) // float - unique solution for x
| ^~~~~~~
Graph.cpp: In member function 'void Node::collect_v_i(std::vector<int>&)':
Graph.cpp:44:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | for(auto[n,t] : neigh) n->collect_v_i(v_i);
| ^
Graph.cpp: In member function 'void Node::set_x(float)':
Graph.cpp:51:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto[n,_] : neigh) n->set_x(x);
| ^
Graph.cpp: In function 'int main()':
Graph.cpp:80:27: error: '__gnu_cxx::__alloc_traits<std::allocator<Node>, Node>::value_type' {aka 'struct Node'} has no member named 'assign'
80 | auto a = nodes[t].assign();
| ^~~~~~
Graph.cpp:103:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 1; i < vi.size(); i++)
| ~~^~~~~~~~~~~
Graph.cpp:110:25: warning: unused variable 'min_cost' [-Wunused-variable]
110 | int min_cost = cost;
| ^~~~~~~~
Graph.cpp:111:25: warning: unused variable 'min_x' [-Wunused-variable]
111 | int min_x = x;
| ^~~~~
