提出 #53140199

---

ソースコード 拡げる

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
#ifdef _MSC_VER
#	include <intrin.h>
#	define __builtin_popcount __popcnt
#endif

#define fi first
#define se second

//#include <atcoder/all>
//using namespace atcoder;
//typedef modint998244353 mint;

using namespace std;

typedef long long int lld;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef vector<int> vi;
typedef vector<lld> vl;
typedef vector<ld> vld;
typedef vector<char> vch;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vivi;
typedef vector<vl> vlvl;
typedef vector<vch> vcvc;
typedef vector<vb> vbvb;
typedef vector<vs> vsvs;

const lld mod = 998244353LL;
const int inf = 1LL << 30;
const int nom = 3000000;

typedef struct node
{
	int b, los;
} node;

int main()
{
	cin.tie(NULL), cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n, m, ln, tp, tp2, tp3, no, now = 0, idx;

	cin >> n >> m;

	vector<vector<node>> vc(n);
	vi comb, rank(n, 0), rev_rank(n, 0), rank_vit(n, 0), now_cnt(n, 0), deg(n), now_deg;
	vivi cnt(n, vi(n, 0));

	for (int i = 0; i < m; ++i)
	{
		cin >> tp >> tp2 >> tp3;

		tp--, tp2--;
		
		deg[tp2]++;
		vc[tp].push_back({ tp2, tp3 });
	}

	for (int i = 0; i < n; ++i)
	{
		if (!deg[i])
			comb.push_back(i);
	}

	ln = (int)comb.size();

	auto rng = default_random_engine{ random_device {}() };
	queue<int> que;

	for (int t = 0; t < nom; ++t)
	{
		shuffle(comb.begin(), comb.end(), rng);

		now++;
		no = 0, idx = n - 1;
		now_deg = deg;

		for (int i = 0; i < ln; ++i)
		{
			while (idx >= 0 && rank_vit[idx] == now)
				idx--;

			if (idx == -1)
			{
				no = 1;

				break;
			}

			tp = comb[i];
			rank[idx] = tp, rev_rank[tp] = idx;
			now_cnt[tp] = rank_vit[idx] = now;

			que.push(tp);

			while (!que.empty())
			{
				tp = que.front();
				que.pop();

				for (int j = 0; j < (int)vc[tp].size(); ++j)
				{
					tp2 = vc[tp][j].b, tp3 = vc[tp][j].los;

					if (rev_rank[tp] - tp3 < 0)
					{
						no = 1;

						break;
					}

					rank[rev_rank[tp] - tp3] = tp2, rev_rank[tp2] = rev_rank[tp] - tp3;
					now_cnt[tp2] = rank_vit[rev_rank[tp] - tp3] = now;
					now_deg[tp2]--;

					if (now_deg[tp2] == 0)
						que.push(tp2);
				}

				if (no)
					break;
			}

			if (no)
				break;
		}

		tp = -1, tp2 = 0;

		for (int i = 0; i < n; ++i)
		{
			if (rank_vit[i] < now)
				tp = i, tp2++;
		}

		if (tp2 >= 2)
			no = 1;
		else if (tp2 == 1)
		{
			for (int i = 0; i < n; ++i)
			{
				if (now_cnt[i] < now)
					tp2 = i;
			}

			rank[tp] = tp2, rev_rank[tp2] = tp;
		}

		if (no)
			continue;

		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < (int)vc[i].size(); ++j)
			{
				if (rev_rank[i] - rev_rank[vc[i][j].b] != vc[i][j].los)
				{
					no = 1;

					break;
				}
			}

			if (no)
				break;
		}

		if (!no)
		{
			for (int i = 0; i < n; ++i)
				cnt[rank[i]][i] = 1;
		}
	}

	for (int i = 0; i < n; ++i)
	{
		tp = -1;
		no = 0;

		for (int j = 0; j < n; ++j)
		{
			if (cnt[i][j])
			{
				if (tp != -1)
					no = 1;

				tp = j;
			}
		}

		if (no || tp == -1)
			cout << -1;
		else
			cout << tp + 1;

		cout << ' ';
	}

	cout << '\n';

	return 0;
}

提出情報

ジャッジ結果