Recover City Profits
National Olympiad — National round
Submission name: trade.cpp
Problem summary
A connected undirected simple graph has N vertices, each of degree two. Each edge stores the arithmetic mean of the unknown profits at its endpoints. Recover all vertex profits, or determine that the system is inconsistent or has multiple solutions. Profits may be negative.
Input
N, then N records u v mean, with at most two decimal digits in each mean.
Output
For a unique solution, N profits in vertex-number order, each with exactly two decimal digits. Otherwise print impossible or too many.
Constraints
3≤N≤100,000; each edge mean has absolute value less than 1000.
Worked example
An independently prepared example for this explanation.
Input
3 1 2 2 2 3 4 3 1 3
Output
1.00 3.00 5.00
Solution analysis
- Represent every mean exactly in cents. An edge gives profit[u]+profit[v]=2·mean.
- Traverse the cycle, expressing each profit as sign[v]·X+offset[v], where X is vertex 1’s profit.
- The closing edge either fixes X (odd cycle), is a redundant equality (even cycle), or contradicts the accumulated offsets.
Why it works
Propagation is equivalent to each traversed edge equation. The remaining closing equation is the only unprocessed constraint. Its coefficient of X is either ±2 or zero, giving exactly the three possible outcomes.
Watch out. Do not use floating-point equality. The statement specifies lowercase impossible, despite a capitalized sample.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Propagation is equivalent to each traversed edge equation. The remaining closing equation
// is the only unprocessed constraint.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<utility>
#include<tuple>
#include<iomanip>
#include<cstdlib>
using namespace std;
long long cents(string s){
bool neg=s[0]=='-';
if(neg||s[0]=='+'){
s=s.substr(1);
}
auto p=s.find('.');
string a=s.substr(0,p),b=p==string::npos?"":s.substr(p+1);
while(b.size()<2){
b+='0';
}
return (neg?-1:1)*(stoll(a)*100+stoll(b));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<pair<int,long long>>>g(n+1);
for(int i=0;i<n;i++){
int u,v;
string s;
cin>>u>>v>>s;
long long w=2*cents(s);
g[u].push_back({v,w});
g[v].push_back({u,w});
}
vector<int>sg(n+1);
vector<long long>b(n+1);
queue<int>q;
sg[1]=1;
q.push(1);
bool fixed=false,bad=false;
long long X=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto[v,w]:g[u]){
if(!sg[v]){
sg[v]=-sg[u];
b[v]=w-b[u];
q.push(v);
}
else{
int c=sg[u]+sg[v];
long long rhs=w-b[u]-b[v];
if(c==0){
if(rhs!=0){
bad=true;
}
}
else{
long long z=rhs/c;
if(rhs%c||(fixed&&X!=z)){
bad=true;
}
X=z;
fixed=true;
}
}
}
}
if(bad){
cout<<"impossible\n";
}
else if(!fixed){
cout<<"too many\n";
}
else{
for(int i=1;i<=n;i++){
long long v=sg[i]*X+b[i];
if(i>1){
cout<<' ';
}
if(v<0){
cout<<'-';
}
v=llabs(v);
cout<<v/100<<'.'<<setw(2)<<setfill('0')<<v%100;
if(i==n){
cout<<'\n';
}
}
}
}