Submission #1146153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146153		arashmemar	Graph (BOI20_graph)	C++20	100 / 100	124 ms	46780 KiB

Graph

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

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

multiset <long long int> fap, fam;

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

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

void dfs(long long 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 (long long int i = 0;i < ne[v].size();i++)
	{
		long long int u = ne[v][i].first, t = ne[v][i].second;	
		if (p[v].size())
		{
			long long int tmp = *p[v].begin();
			m[u].insert(t - tmp);
		}
		if (m[v].size())
		{
			long long 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);
	long long int n, ms;
	cin >> n >> ms;
	for (long long int i = 1;i <= ms;i++)
	{
		long long int v, u, c;
		cin >> v >> u >> c;
		c *= 2;
		ne[v].push_back({u, c});
		ne[u].push_back({v, c});
	}

	for (long long 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())
		{
			long long 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;
		}

	
		long long int pre = 1e6;
		long long int s = (long long int)2 * pre * cv.size();
		int ch = cv.size();

		for (auto o : cv)
		{
			if (p[o].size())
			{
				fap.insert(-(*p[o].begin()));
				s -= *p[i].begin();
			}
			else
			{
				fam.insert(*m[o].begin());
				s += *m[i].begin();
			}
		}

		auto it1 = fap.begin(), it2 = fam.begin();

		while ((it1 != fap.end() or it2 != fam.end()) and ch > 0)
		{
			long long int cur;
			if (it1 != fap.end() and (it2 == fam.end() or (*it1) < (*it2)))
			{
				cur = *it1;
				it1++;
			}
			else
			{
				cur = *it2;
				it2++;
			}
			s -= (cur - pre) * ch;
			ch -= 2;
			pre = cur;
		}

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

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

	cout << "YES" << endl;

	for (long long int i = 1;i <= n;i++)
	{
		if (rans[i] == -1)
		{
			cout << '-';
		}
		cout << rans[i] / 2;
		if (rans[i] % 2)
		{
			cout << ".5";
		}
		cout << ' ';
	}
}

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