Submission #1146104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146104		arashmemar	Graph (BOI20_graph)	C++20	5 / 100	6 ms	12104 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;

set <int> p[maxn], m[maxn], ans;

vector <pair <int, int>> ne[maxn];
bool mark[maxn], hans = 1;
vector <int> cv;
int rans[maxn];

struct cmp
{
	bool operator() (int a, int b)const
	{
		return abs(a) < abs(b);
	}
};

void dfs(int v)
{
	cv.push_back(v);
	mark[v] = 1;
	if (p[v].size() > 1 or m[v].size() > 1 or hans == 0)
	{
		hans = 0;
		return ;
	}

	if (p[v].size() and m[v].size())
	{
		ans.insert(((*m[v].begin()) - (*p[v].begin())) / 2);
	}

	for (int i = 0;i < ne[v].size();i++)
	{
		int u = ne[v][i].first, t = ne[v][i].second;	
		if (p[v].size())
		{
			int tmp = *p[v].begin();
			m[u].insert(t - tmp);
		}
		if (m[v].size())
		{
			int tmp = *m[v].begin();
			p[u].insert(t - tmp);
		}
		if (!mark[u])
		{
			dfs(u);
		}
	}

	if (p[v].size() > 1 or m[v].size() > 1 or hans == 0)
	{
		hans = 0;
		return ;
	}

	if (p[v].size() and m[v].size())
	{
		ans.insert(((*m[v].begin()) - (*p[v].begin())) / 2);
	}

	return ;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, ms;
	cin >> n >> ms;
	for (int i = 1;i <= ms;i++)
	{
		int v, u, c;
		cin >> v >> u >> c;
		c *= 2;
		ne[v].push_back({u, c});
		ne[u].push_back({v, c});
	}

	for (int i = 1;i <= n;i++)
	{
		if (mark[i])
		{
			continue;
		}
		p[i].insert(0);
		dfs(i);

		if (!hans or ans.size() > 1)
		{
			cout << "NO" << '\n';
			return 0;
		}

		if (ans.size())
		{
			int tmp = (*ans.begin());
			for (auto o : cv)
			{
				if (p[o].size())
				{
					rans[o] = tmp + (*p[o].begin());
				}
				else
				{
					rans[o] = -tmp + (*m[o].begin());
				}
			}
			ans.clear();
			cv.clear();
			continue;
		}

		multiset <int, cmp> tmp;

		for (auto o : cv)
		{
			if (p[o].size())
			{
				tmp.insert(-(*p[o].begin()));
			}
			else
			{
				tmp.insert(*m[o].begin());
			}
		}

		auto it = tmp.begin();

		for (int i = 0;i < tmp.size() / 2;i++)
		{
			it++;
		}

		ans.insert(*it);

		int tmp2 = (*ans.begin());
		for (auto o : cv)
		{
			if (p[o].size())
			{
				rans[o] = tmp2 + (*p[o].begin());
			}
			else
			{
				rans[o] = -tmp2 + (*m[o].begin());
			}
		}


		ans.clear();
		cv.clear();
	}

	cout << "YES" << endl;

	for (int i = 1;i <= n;i++)
	{
		cout << (float)rans[i] / 2 << ' ';
	}
}

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