Submission #974001

#	Time	Username	Problem	Language	Result	Execution time	Memory
974001		Onur_Ilgaz	Graph (BOI20_graph)	C++17	100 / 100	123 ms	28768 KiB

Graph

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 100001;
vector <pair<int, int> > adj[N];
int root[N], sign[N];
bitset <N> cons;
double val[N], add[N];
vector <double> idk;

double calc(int node) {
	return val[node] + add[root[node]] * sign[node];
}

void dfs1(int node, int comp, bool sgn) { // constant olabilenleri constant yap
	sign[node] = sgn ? 1 : -1;
	root[node] = comp;
	idk.push_back(val[node] * sign[node]);
	for(auto [to, w]:adj[node]) {
		if(!root[to]) {
			val[to] = w - val[node];
			dfs1(to, comp, !sgn);
		}
		else {
			if(cons[root[node]]) {
				if(calc(node) + calc(to) != w) {
					cout << "NO";
					exit(0);
				}
			}
			else {
				if(sign[node] == sign[to]) {
					cons[root[node]] = 1;
					double diff = w - (val[node] + val[to]);
					add[root[node]] = diff / 2 * sign[node];
				}
				else {
					if(val[node] + val[to] != w) {
						cout << "NO";
						exit(0);
					}
				}
			}
		}
	}
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	for(int i = 1; i <= n; i++) {
		if(root[i]) continue;
		idk.clear();
		dfs1(i, i, 1);
		// if inconsistent, then do some value adjustments
		if(!cons[i]) {
			sort(idk.begin(), idk.end());
			double midi = idk[idk.size() / 2];
			add[i] = -midi;
			//cout << midi << "\n";
		}
	}
	cout << "YES\n";

	for(int i = 1; i <= n; i++) {
		cout << calc(i) << " ";
	}
}

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