Submission #1292055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292055		mdobric	Graph (BOI20_graph)	C++20	100 / 100	134 ms	25708 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n, m;
vector <pair <int, double> > v[maxn];
vector <int> novi;
double znak[maxn], dodaj[maxn];
int poc[maxn], ans;
double val[maxn];
int fiks[maxn];

void dfs (int x){
	novi.push_back(x);
	for (int i = 0; i < v[x].size(); i++){
		int y = v[x][i].first;
		double suma = v[x][i].second;
		double noviznak = -znak[x];
		double novidodaj = suma - dodaj[x];
		if (poc[y] != -1){
			if (znak[x] == znak[y]){
				double novival = (suma - dodaj[x] - dodaj[y]) / (2 * znak[x]);
				if (fiks[poc[x]] == 0){
					fiks[poc[x]] = 1;
					val[poc[x]] = novival;
				}
				else if (val[poc[x]] != novival) ans = 1;
			}
			else if (dodaj[x] + dodaj[y] != suma) ans = 1;
		}
		else{
			poc[y] = poc[x];
			znak[y] = noviznak;
			dodaj[y] = novidodaj;
			dfs(y);
		}
	}
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}
	memset(poc, -1, sizeof poc);
	for (int i = 1; i <= n; i++){
		if (poc[i] == -1){
			poc[i] = i;
			znak[i] = 1;
			dodaj[i] = 0;
			dfs(i);
			if (fiks[i] == 0){
				int low = -2*m, high = 2*m, mid;
				while (low < high){
					//cout << low << " " << high << endl;
					if (low + high < 0) mid = (low + high - 1) / 2;
					else mid = (low + high) / 2;
					//cout << mid << endl;
					int sum1 = 0, sum2 = 0;
					for (int j = 0; j < novi.size(); j++){
						sum1 += abs(znak[novi[j]] * mid + dodaj[novi[j]]);
						sum2 += abs(znak[novi[j]] * (mid + 1) + dodaj[novi[j]]);
					}
					if (sum1 < sum2) high = mid;
					else low = mid + 1;
				}
				val[i] = low;
				
			}
			for (int j = 0; j < novi.size(); j++){
				val[novi[j]] = znak[novi[j]] * val[i] + dodaj[novi[j]];
			}
			novi.clear();
		}
	}
	if (ans == 1){
		cout << "NO" << "\n";
		return 0;
	}
	cout << "YES" << "\n";
	for (int i = 1; i <= n; i++){
		cout << fixed << setprecision(7);
		cout << val[i] << " ";
	}
	cout << "\n";
	
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5