Submission #859361

#	Time	Username	Problem	Language	Result	Execution time	Memory
859361		maks007	Village (BOI20_village)	C++14	0 / 100	1 ms	348 KiB

Village

#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long
 
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector <pair <int, double>> g[n];
	vector <double> node(n, (double)1e9), ans(n);
	double mn = 1e9;
	vector <int> v;
	function<void(int)> dfs=[&](int v) {
		node[v] = 0;
		for(auto [i, j] : g[v]) {
			if(!node[i]) continue;
			dfs(i);
		}
	};
	function <int(int,double)> check=[&](int v, double color) {
		node[v] = color;
		// cout << v << " " << color << "\n";
		int f = 1;
		for(auto [i,j] : g[v]) {
			if(node[i] == 1e9) f = min(f, check(i, j-color));
			else {
				if(node[v] + node[i] != j) f = 0;
			} 
		}
		return f;
	};
	function<void(int, int)> rec=[&](int i, int sum) {
		if(i == v.size()) {
			if(mn > sum) {
				mn = sum;
				ans = node;
			}	
			return;
		}
		for(double val = -2; val <= 2; val += 0.25) {
			for(auto &j : node) j = 1e9;
			if(check(v[i], val)) {
				// cout << val << " " << i << "\n";
				node[v[i]] = val;
				rec(i + 1, sum + fabs(val));
				node[v[i]] = 1e9;
			}
				// cout << "\n";
		}
	};
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		int w;
		cin >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 0; i < n; i ++) {
		if(node[i] == 1e9) {dfs(i);v.push_back(i);}
	}
	// for(auto i : v) cout << i << " ";
	for(auto &j : node) j = 1e9;
	rec(0, 0);
	if(mn == 1e9) cout << "NO";
	else {
		cout << "YES\n";
		for(auto i : ans) cout << fixed << setprecision(6) << i << " ";
	}
	return 0;
}

Compilation message (stderr)

Village.cpp: In lambda function:
Village.cpp:18:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |   for(auto [i, j] : g[v]) {
      |            ^
Village.cpp: In lambda function:
Village.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |   for(auto [i,j] : g[v]) {
      |            ^
Village.cpp: In lambda function:
Village.cpp:36:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(i == v.size()) {
      |      ~~^~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50