Submission #802094

#	Time	Username	Problem	Language	Result	Execution time	Memory
802094		parsadox2	Graph (BOI20_graph)	C++14	100 / 100	150 ms	27904 KiB

Graph

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

const int maxn = 1e5 + 10;
const long long inf = 1e18;
int n , m;
double ar[maxn] , x;
vector <pair<int , int>> adj[maxn];
pair<int , int> dis[maxn];
bool marked[maxn] , flg;
vector <int> trav;

void dfs(int v)
{
	marked[v] = true;
	trav.push_back(v);
	for(auto e : adj[v])
	{
		int u = e.first , w = e.second;
		if(!marked[u])
		{
			dis[u].first = w - dis[v].first;
			dis[u].second = -1 * dis[v].second;
			dfs(u);
		}
		else if(dis[u].second == dis[v].second)
		{
			flg = true;
			x = w - dis[u].first - dis[v].first;
			x = 1.0 * x / 2;
			if(dis[u].second == -1)
				x *= -1;
		}
		else if(dis[u].first + dis[v].first != w)
		{
			cout << "NO" << '\n';
			exit(0);
		}
	}
}

void solve(int v)
{
	flg = false;
	dis[v] = make_pair(0 , 1);
	trav.clear();
	dfs(v);
	if(flg)
	{
		for(auto u : trav)
		{
			ar[u] = dis[u].first;
			ar[u] += 1.0 * dis[u].second * x;
		}
		for(auto u : trav)  for(auto e : adj[u])  if(ar[u] + ar[e.first] != e.second)
		{
			cout << "NO" << '\n';
			exit(0);
		}
		return;
	}
	vector <int> ngt , pst;
	for(auto u : trav)
	{
		if(dis[u].second == -1)
			ngt.push_back(dis[u].first);
		else
			pst.push_back(dis[u].first);
	}
	vector <int> pngt , ppst;
	sort(ngt.begin() , ngt.end());
	sort(pst.begin() , pst.end());
	pngt.push_back(0);
	ppst.push_back(0);
	for(auto u : ngt)
		pngt.push_back(pngt.back() + u);
	for(auto u : pst)
		ppst.push_back(ppst.back() + u);
	int ili = trav.size();
	long long sum = inf;
	for(int i = -2 * ili ; i <= 2 * ili ; i++)
	{
		int tmp = lower_bound(pst.begin() , pst.end() , -i) - pst.begin();
		long long now = 0;
		now -= ppst[tmp];
		now -= tmp * i;
		now += (ppst.back() - ppst[tmp]);
		now += (ppst.size() - tmp) * i;
		int j = -i;
		tmp = lower_bound(ngt.begin() , ngt.end() , -j) - ngt.begin();
		now -= pngt[tmp];
		now -= tmp * j;
		now += (pngt.back() - pngt[tmp]);
		now += (pngt.size() - tmp) * j;
		if(now < sum)
		{
			sum = now;
			x = i;
		}
	}
	for(auto u : trav)
	{
		ar[u] = dis[u].first;
		ar[u] += 1.0 * dis[u].second * x;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		int v , u , w;  cin >> v >> u >> w;
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
	}
	for(int i = 1 ; i <= n ; i++)  if(!marked[i])
		solve(i);
	cout << "YES" << '\n';
	cout << setprecision(1) << fixed;
	for(int i = 1 ; i <= n ; i++)
		cout << ar[i] << " ";
	cout << '\n';
	return 0;
}

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