Submission #257267

#	Time	Username	Problem	Language	Result	Execution time	Memory
257267		maximath_1	Graph (BOI20_graph)	C++11	100 / 100	449 ms	45576 KiB

Graph

/*
	* BOI 2020 2A: Graph
	* Set a variable x on one vertex
	* Express values of all vertices in terms of x
	* If there is colliding information, no solution
	* Else, take the minimum of the sum
	* Ah also do that for every connected component :|
*/
//I have started to include headers one by one
//Because I need to wait like a minute for it to compile in my pc
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <deque>
#include <iostream>
#include <limits>
#include <string>
#include <tuple>
#include <iterator>
#include <complex>
#include <random>
#include <iomanip>
using namespace std;
 
#define ll long long
#define ld long double
const ll inf = 1e18;
const ld eps = 1e-6;
struct eq{
	ld m, c; //mx + c
	eq(){}
	eq(ld a, ld b) : m(a) , c(b) {}
 
	eq& operator+=(const eq&rhs){m += rhs.m, c += rhs.c; return *this;}
	eq& operator-=(const eq&rhs){m -= rhs.m, c -= rhs.c; return *this;}
	friend eq operator+(eq a, const eq& b) {return a += b;}
	friend eq operator-(eq a, const eq& b) {return a -= b;}
};
 
ld solv(eq a, eq b){
	//a.m x + a.c = b.m x + b.c
	if(abs(a.m - b.m) < eps){
		if(abs(a.c - b.c) > eps) return -(ld)inf; //no solution
		else return (ld)inf; //inf many solution
	}
	return (ld)(b.c - a.c) / (ld)(a.m - b.m); //one solution
}
ld f(eq a, ld x){
	return (ld)a.m * x + (ld)a.c;
}
 
int n, m;
eq nod[100005];
ld x; //var
vector<pair<int, int> > adj[100005];
bitset<100005> vis;
vector<int> cc;
ld ans[100005];
bool x_found = false, fail_condition = false;
 
void dfs(int nw, int bf, eq cr){
	if(fail_condition) return; //pretty much self explanatory
	if(vis[nw]){
		//compare the existing equation with the new one
		ld get = solv(nod[nw], cr);
		if(abs(get) < eps) get = 0.0; //you know those -0.0? yea to deal with that
		if(abs(get + inf) < eps) fail_condition = true; //no sol
		else if(abs(get - (ld)inf) > eps){
			if(x_found && abs(x - get) > eps) fail_condition = true; //conflicting x val
			else{
				x = get; x_found = true; //x found
			}
		}
		return;
	}
 
	cc.push_back(nw);
	nod[nw] = cr; vis[nw] = 1;
	for(pair<int, int> nx : adj[nw]) if(nx.first != bf){
		eq nex(0, nx.second);
		nex -= nod[nw];
		dfs(nx.first, nw, nex);
	}
	return;
}
 
unordered_map<ll, int> viss;
ll hash_(int a, int b){
	return a * 200005ll + b;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(10);
 
	//read
	cin >> n >> m;
	for(int u, v, w, i = 0; i < m; i ++){
		cin >> u >> v >> w;
		if(viss[hash_(u, v)]){
			if(viss[hash_(u, v)] == w) continue;
			cout << "NO\n";
			return 0;
		}
		viss[hash_(u, v)] = viss[hash_(v, u)] = w;
		adj[u].push_back({v, w});
		if(u != v) adj[v].push_back({u, w});
	}
 
	//solve
	vis = 0;
	for(int i = 1; i <= n; i ++) if(!vis[i]){
		cc.clear(); x_found = false;
		dfs(i, i, eq(1, 0));
		if(fail_condition) break;
		if(!x_found){
			//check annoying self-loops >:V
			bool flag = false;
			for(int j : cc){
				if(viss[hash_(j, j)]){
					x = solv(nod[j], eq(0, (ld)viss[hash_(j, j)] / 2.0));
					flag = true; break;
				}
			}
			if(!flag){
				//This point, you can do slope trick, ternary search or whatever
				//Easiest is to take the median of the values
				vector<ld> values;
				for(int j : cc) values.push_back(solv(nod[j], eq(0, 0)));
				sort(values.begin(), values.end());
				if(values.size() % 2 == 0)
					x = values[values.size() / 2] + values[values.size() / 2 - 1];
				else
					x = values[values.size() / 2] + values[values.size() / 2];
				x /= (ld)2.0;
			}
		}
		for(int j : cc) ans[j] = f(nod[j], x);
	}
 
	for(int i = 1; i <= n; i ++){
		for(pair<int, int> j : adj[i]){
			if(abs((ld)ans[i] + (ld)ans[j.first] - (ld)j.second) > eps){
				printf("NO\n"); return 0;
			}
		}
	}
 
	//print
	if(fail_condition) cout << "NO\n";
	else{
		cout << "YES\n";
		for(int i = 1; i <= n; i ++)
			cout << ans[i] << " ";
	}
	return 0;
}

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